给出一张棋盘，其上一些位置上有一些棋子。现在又给出一些限制条件，如某行以下最多可以选取多少的棋子，某列以右最多可以选取多少棋子。每个棋子的位置按照一定的顺序给出，其顺序中的排名即是其价值，问可以达到的最大价值是多少
非常常规的思路，将行和列拆开，如果在某个位置有一个点则将其行和列连接上一条边，其容量为1，边权为其标号。但是行和列很多，所以还需要对行和列进行离散化。每个离散化出的行与其上一行，每个列与其左边的一个列之间都有可以有若干条限制，选取其中最小的限制即是限制离散化出来的点的流量的限制根据每个点的限制，将其与上一点点之间连接上容量为限制，价值为0的边，最后跑费用流即可
感谢山东理工大学的一位同学，原代码可以通过
5 1 2 2 2 3 1 100 100 3 2 5 R 2 3 C 1 4 R 3 1 C 2 2 C 5 0叉掉。理由是，简单地使用费用流得到的答案会优先保证最大的流量，而有时可能会选择更少但是权值更大的点，且其为正解，解决方案是在网络流更新增广路时，当距离为正就停止更新。这样就可以得到最大费用。正解已更新
#include<bits/stdc++.h> using namespace std; const int sizep=505; const int inf=0x3f3f3f3f; const int maxn=2005; const int maxm=2e5+5; struct Edge{ int to,next,flow,cost; int cap; } edge[maxm]; int head[maxn],tol; int pre[maxn]; int dis[maxn]; bool vis[maxn]; int N; void init(int n) { N=n;tol=0; for(int i=0;i<n;i++) head[i]=-1; } void AddEdge(int u,int v,int cap,int cost) { edge[tol].to=v; edge[tol].cap=cap; edge[tol].cost=cost; edge[tol].flow=0; edge[tol].next=head[u]; head[u]=tol++; edge[tol].to=u; edge[tol].cap=0; edge[tol].flow=0; edge[tol].cost=-cost; edge[tol].next=head[v]; head[v]=tol++; } bool spfa(int s,int t) { queue<int >q; for(int i=0;i<=N;++i) { dis[i]=inf; vis[i]=false; pre[i]=-1; } dis[s]=0; vis[s]=true; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap>edge[i].flow && dis[v]>dis[u]+edge[i].cost) { dis[v]=dis[u]+edge[i].cost; pre[v]=i; if(!vis[v]) { vis[v]=true; q.push(v); } } } } if(pre[t]==-1) return false; else return true; } int MincostMaxflow(int s,int t,int &cost) { int flow=0; cost=0; while(spfa(s,t)) { if(dis[t]>0) break; int Min=inf; for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]) { if(Min>edge[i].cap -edge[i].flow) Min=edge[i].cap -edge[i].flow; } for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]) { edge[i].flow+=Min; edge[i^1].flow-=Min; cost+=edge[i].cost*Min; } flow+=Min; } return flow; } struct point{ int x,y; point(){} point(int x,int y):x(x),y(y){} }; struct limit{ int loc; int cap; limit(){} limit(int loc,int cap):loc(loc),cap(cap){} bool friend operator<(limit a,limit b) { return a.loc<b.loc; } }; point p[sizep]; int capx[sizep],capy[sizep]; vector<limit> limx,limy; vector<int> vx; vector<int> vy; int idx[sizep]; int idy[sizep]; int main() { int n; int x,y; while(~scanf("%d",&n)) { vx.clear(); vy.clear(); limx.clear(); limy.clear(); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); p[i]=point(x,y); vx.push_back(x); vy.push_back(y); } sort(vx.begin(),vx.end()); sort(vy.begin(),vy.end()); vx.erase(unique(vx.begin(),vx.end()),vx.end()); vy.erase(unique(vy.begin(),vy.end()),vy.end()); for(int i=1;i<=n;i++) { idx[i]=lower_bound(vx.begin(),vx.end(),p[i].x)-vx.begin()+1; idy[i]=lower_bound(vy.begin(),vy.end(),p[i].y)-vy.begin()+1; } int totx,toty; totx=vx.size(),toty=vy.size(); int s=0,t=totx+toty+1; int m; scanf("%d",&m); char op[5]; int loc,k; for(int i=1;i<=m;i++) { scanf("%s%d%d",op,&loc,&k); if(op[0]=='R') { limx.push_back(limit(loc,k)); } if(op[0]=='C') { limy.push_back(limit(loc,k)); } } sort(limx.begin(),limx.end()); sort(limy.begin(),limy.end()); int cntx=0,cnty=0; memset(capx,inf,sizeof(capx)); memset(capy,inf,sizeof(capy)); for(int i=0;i<limx.size();i++) { while(cntx<totx-1&&vx[cntx]<limx[i].loc) { cntx++; } capx[cntx+1]=min(capx[cntx+1],limx[i].cap); } for(int i=0;i<limy.size();i++) { while(cnty<toty-1&&vy[cnty]<limy[i].loc) { cnty++; } capy[cnty+1]=min(capy[cnty+1],limy[i].cap); } init(totx+toty+2); for(int i=1;i<=n;i++) { AddEdge(idx[i],idy[i]+totx,1,-i); } for(int i=1;i<=totx;i++) { AddEdge(i-1,i,capx[i],0); } for(int i=1;i<=toty;i++) { if(i==1) AddEdge(totx+i,t,capy[i],0); else AddEdge(totx+i,totx+i-1,capy[i],0); } int cost=0; MincostMaxflow(s,t,cost); printf("%d\n",-cost); } }