比赛场上很容易想到是费用流,但是没有想到建图方法qwq,太弱了。

这里直接贴官方题解:

费用流。离散化坐标,每行用一个点表示,每列也用一个点表示。表示第i-1行的点向表示第i行的点连边,容量为第i行及以后能拿的棋子数的上限,费用为0,同理表示相邻列的点两两连边。若第i行第j列上有棋子,则表示第i行的点向表示第j列的点连边,容量为1,费用为该棋子的价值。可以定义源点表示第0行,汇点表示第0列,源点到汇点的最大费用流即为答案。

就是按照题解的建图方法,还有一些小细节:先要排序排除无用限制来减少限制边数,不然会超时。我用的办法是,按限制从小到大排序,大限制当且仅当它的行数小于小限制行数时才有用。列同理。这里想不明白的建议画图细细想。然后就是连边来表示限制条件:行的话就是(i-1)->i行连边,列的话就是i->(i-1)列连边,这是因为0行是源点0列是汇点所致的,行点要靠它的入边来限制流量,列点要靠出边来限制流量。

细节详见代码及注释:

#include<bits/stdc++.h>
using namespace std;
const int N=+;
const int M=+;
const int INF=0x3f3f3f3f;
int n,m,r,c,s,t,maxflow,mincost;
int nx,ny,x[N],y[N],xx[N],yy[N],bx[N],by[N];
struct edge{
int nxt,to,cap,cost;
}edges[M<<];
int cnt=,head[N],pre[N]; struct dat{ int t,l; } R[M],C[M];
bool cmp(dat a,dat b) { return a.l<b.l || a.l==b.l && a.t<b.t; } void add_edge(int x,int y,int z,int c) {
edges[++cnt].nxt=head[x]; edges[cnt].to=y; edges[cnt].cap=z; edges[cnt].cost=c; head[x]=cnt;
} queue<int> q;
int dis[N],lim[N];
bool inq[N];
bool spfa(int s,int t) {
while (!q.empty()) q.pop();
memset(dis,0x3f,sizeof(dis));
memset(inq,,sizeof(inq));
dis[s]=; inq[s]=; lim[s]=INF; q.push(s);
while (!q.empty()) {
int x=q.front(); q.pop();
for (int i=head[x];i;i=edges[i].nxt) {
edge e=edges[i];
if (e.cap && dis[x]+e.cost<dis[e.to]) {
dis[e.to]=dis[x]+e.cost;
pre[e.to]=i; //即e.to这个点是从i这条边来的
lim[e.to]=min(lim[x],e.cap);
if (!inq[e.to]) { q.push(e.to); inq[e.to]=; }
}
}
inq[x]=;
}
return !(dis[t]==INF);
} void MCMF() {
maxflow=; mincost=;
while (spfa(s,t)) {
int now=t;
maxflow+=lim[t];
mincost+=lim[t]*dis[t];
while (now!=s) {
edges[pre[now]].cap-=lim[t];
edges[pre[now]^].cap+=lim[t];
now=edges[pre[now]^].to;
}
}
} int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d%d",&x[i],&y[i]),bx[i]=x[i],by[i]=y[i];
nx=ny=n;
scanf("%d",&m);
char opt[];
for (int i=;i<=m;i++) {
int tx,ty; scanf("%s%d%d",opt,&tx,&ty);
if (opt[]=='R') R[++r]=(dat){tx,ty};
if (opt[]=='C') C[++c]=(dat){tx,ty};
}
int tmp=;
sort(R+,R+r+,cmp);
for (int i=;i<=r;i++) //排除行无用限制
if (tmp== || R[i].t<R[tmp].t) R[++tmp]=R[i],bx[++nx]=R[i].t;
r=tmp; tmp=;
sort(C+,C+c+,cmp);
for (int i=;i<=c;i++) //排除列无用限制
if (tmp== || C[i].t<C[tmp].t) C[++tmp]=C[i],by[++ny]=C[i].t;
c=tmp; sort(bx+,bx+nx+); nx=unique(bx+,bx+nx+)-(bx+); //离散化
sort(by+,by+ny+); ny=unique(by+,by+ny+)-(by+); //离散化 for (int i=;i<=n;i++) {
int tx=lower_bound(bx+,bx+nx+,x[i])-bx;
int ty=lower_bound(by+,by+ny+,y[i])-by;
add_edge(tx,nx++ty,,-i); add_edge(nx++ty,tx,,i); //棋子连边
}
memset(xx,0x3f,sizeof(xx));
memset(yy,0x3f,sizeof(yy));
for (int i=;i<=r;i++) {
int tx=lower_bound(bx+,bx+nx+,R[i].t)-bx;
xx[tx]=min(xx[tx],R[i].l); //先求好限制条件,xx[i]代表i行及以后的最小限制
}
for (int i=;i<=c;i++) {
int ty=lower_bound(by+,by+ny+,C[i].t)-by;
yy[ty]=min(yy[ty],C[i].l); //列同行同理
}
//这里是关键:行i-1->i为了限制i的出流,列i->i-1为了限制i的出流
for (int i=;i<=nx;i++) add_edge(i-,i,xx[i],),add_edge(i,i-,,);
for (int i=;i<=ny;i++) add_edge(nx++i,nx++i-,yy[i],),add_edge(nx++i-,nx++i,,); s=; t=nx+;
MCMF();
cout<<-mincost<<endl;
return ;
}

最新文章

  1. NSIS 打包脚本基础
  2. tornado+sqlalchemy+celery,数据库连接消耗在哪里
  3. 由ASP.NET所谓前台调用后台、后台调用前台想到HTTP——理论篇
  4. 从C#到Objective-C,循序渐进学习苹果开发(5)--利用XCode来进行IOS的程序开发
  5. 分布式搜索引擎Elasticsearch PHP类封装 使用原生api
  6. Spring(七)持久层
  7. Libsvm的MATLAB调用和交叉验证
  8. 深入理解Java虚拟机 - 垃圾收集概述
  9. C# 解析js方法,并调用js方法
  10. IP转发和子网路由
  11. Nginx的启动脚本
  12. QR码生成原理
  13. 剑指Offer-构建乘积数组
  14. Matting任务里的Gradient与Connectivity指标
  15. 【dataX】阿里开源ETL工具——dataX简单上手
  16. (转) The care and maintenance of your adviser
  17. November 04th, 2017 Week 44th Saturday
  18. C#, CLR, and .NET Framework versions
  19. MatchText MatchStr 区别
  20. Spring声明式事务管理(基于XML方式实现)

热门文章

  1. JQuery 获取表格table所有行第一列
  2. SET CONSTRAINTS - 设置当前事务的约束模式
  3. 力扣 ——3Sum python (三数之和)实现
  4. 解决PageHelper.startPage(page, size)后,关于PageInfo的total等属性不正确等问题
  5. 搭建ceph集群(单节点)
  6. nucleus学习
  7. 网站运行一段时间后就无法访问,重启Tomcat才能恢复
  8. 为何使用Html5+CSS3
  9. 常用跨域方法总结(2)——CORS
  10. Django中的HttpRequsest 和Httpresponse对象