题意：给你一个棋盘，棋盘上有一些棋子，有一些规定，规定超过多少行或者多少列后只能取不超过k的棋子。
题解：棋盘问题是一个很经典的网络流问题。
建图还是比较好想的，但是不会跑最大费用流，赛后补了一下。
但是好像这道题有问题，最大费用最大流也能过。
但是明显不符合费用最大时流最大。
所以想一下最小费用最大流的做法，首先费用取反，这样就变成了最小费用，
每次跑一条s到t的最短路，然后减去这条路的流量。这样保证每次跑出来的最短路是越来越大的。
所以当最短路第一次大于0时，接下来所有的流量的费用都大于0，会使费用变大，所以直接跳出。
建图的话，感觉类似并查集的思路，我想了一种很low的建法，题解的建法就很优美了，所以又照着题解建了一波。
#include <bits/stdc++.h> using namespace std; #define N 4010 #define inf 0x3f3f3f3f #define go(i,a,b) for(int i=(a);i<=(b);i++) #define dep(i,a,b) for(int i=(a);i>=(b);i--) struct no{ int to,n,cap,flow,cost; };no d[N*10]; queue<int>q; int h[N],dp[N],p[N],f[N],in[N], tot,need; void add(int u,int to,int w,int v){ //cout<<u<<' '<<to<<' '<<w<<' '<<v<<'+'<<endl; d[tot]={to,h[u],w,0,v };h[u]=tot++; d[tot]={u,h[to],0,0,-v};h[to]=tot++; } bool spfa(int s,int e){ memset(dp,inf,sizeof(dp)); memset(p,-1,sizeof(p)); memset(f,0,sizeof(f)); q.push(s);dp[s]=0; while(!q.empty()){ int x=q.front();q.pop(); f[x]=0; for(int i=h[x];i!=-1;i=d[i].n){ int to=d[i].to,cost=d[i].cost; if(dp[x]+cost<dp[to]&&d[i].cap>d[i].flow){ p[to]=i; dp[to]=dp[x]+cost; if(f[to])continue; f[to]=1; q.push(to); } } } return p[e]!=-1&&dp[e]<0; } int Cost = 0, Flow = 0; int dini(int s,int e){ while(spfa(s,e)){ int Min=inf; for(int i=p[e];i!=-1;i=p[d[i^1].to]) Min=min(Min,d[i].cap-d[i].flow); for(int i=p[e];i!=-1;i=p[d[i^1].to]){ d[i].flow+=Min; d[i^1].flow-=Min; Cost+=d[i].cost*Min; } Flow+=Min; } } int discre(int a[],int n){ sort(a+1,a+n+1); //go(i,1,n)cout<<a[i]<<' ';cout<<endl; return unique(a+1,a+n+1)-a-1; } inline int getdiscre(int a[],int n,int w){ return lower_bound(a+1,a+n+1,w)-a; } int n,m,c_siz,r_siz; inline int cid(int x){return x; } inline int rid(int x){return x+c_siz+1; } char op[10]; int c1[N],c2[N],r1[N],r2[N],id,k,x[N],y[N]; int main() { cin>>n; memset(c2,inf,sizeof(c2)); memset(r2,inf,sizeof(r2)); memset(h,-1,sizeof(h)); go(i,1,n) scanf("%d%d",&x[i],&y[i]), c1[i]=x[i],r1[i]=y[i]; c_siz=discre(c1,n),r_siz=discre(r1,n); go(i,1,n)add(cid(getdiscre(c1,c_siz,x[i])),rid(getdiscre(r1,r_siz,y[i])),1,-i); cin>>m; go(i,1,m){ scanf("%s%d%d",op,&id,&k); if(op[0]=='C'){ id=getdiscre(r1,r_siz,id); if(id<=r_siz)r2[id]=min(r2[id],k); } else { id=getdiscre(c1,c_siz,id); if(id<=c_siz)c2[id]=min(c2[id],k); } } dep(i,c_siz,1) add(cid(i-1),cid(i),c2[i],0); dep(i,r_siz,1) add(rid(i),rid(i-1),r2[i],0); dini(0,c_siz+1); printf("%d\n",-Cost); }
