有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
基本构图没有问题就是构造二分图，但是他问最少放几个，直接那样跑网络流感觉不对，实际上问题就等价于最多能不放几个点，第i行至少放k个点就是第i行最多挖n-k个点，然后把障碍物处理一下就好
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<queue> using namespace std; const int N=32005; const int inf=0x3f3f3f3f; int n,m,x[105],y[105],mp[105][105]; int head[205],cur[205],tot,ans,s,t; int lev[205]; struct aa { int to,pre,flow,cap; }edge[N]; void addedge(int x,int y,int c) { edge[++tot].to=y;edge[tot].pre=head[x];head[x]=tot;edge[tot].cap=c; edge[++tot].to=x;edge[tot].pre=head[y];head[y]=tot;edge[tot].cap=0; } bool bfs() { memset(lev,0,sizeof(lev)); queue<int> q;lev[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for (int i=head[u];i;i=edge[i].pre) if (!lev[edge[i].to]&&edge[i].cap>edge[i].flow) { lev[edge[i].to]=lev[u]+1; if(edge[i].to==t) return true; q.push(edge[i].to); } } return false; } int dfs(int u,int maxflow) { if (u==t||maxflow==0) return maxflow; int ans=0; for (int &i=cur[u];i;i=edge[i].pre) if (lev[edge[i].to]==lev[u]+1) { int flow=dfs(edge[i].to,min(maxflow,edge[i].cap-edge[i].flow)); ans+=flow; maxflow-=flow; edge[i].flow+=flow; edge[((i-1)^1)+1].flow-=flow; if (maxflow==0) return ans; } return ans; } void work() { while(bfs()) { for (int i=s;i<=t;i++) cur[i]=head[i]; ans+=dfs(s,inf); } } int main() { int tt,p,xx,yy; scanf("%d%d%d",&n,&m,&p); for (int i=1;i<=n;i++) { scanf("%d",&tt); x[i]=m-tt; } for (int i=1;i<=m;i++) { scanf("%d",&tt); y[i]=n-tt; } for (int i=1;i<=p;i++) { scanf("%d%d",&xx,&yy); mp[xx][yy]=1; x[xx]--,y[yy]--; } bool o=true; for (int i=1;i<=n;i++) if (x[i]<0) o=false; for (int i=1;i<=m;i++) if (y[i]<0) o=false; if (!o){printf("JIONG!");return 0;} s=0,t=n+m+1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (mp[i][j]==0) addedge(i,j+n,1); for (int i=1;i<=n;i++) addedge(s,i,x[i]); for (int i=1;i<=m;i++) addedge(i+n,t,y[i]); work(); printf("%d",n*m-p-ans); return 0; }总结
1：网络流的题目必须仔细计算有多少边！防止数组溢出。
2：有的时候正向是做不了的，那么转化一下思路，将其通过互补的思考，思考逆向他是等价于什么的。
这道题最少放k个，就是等价于最多挖n-k个空，这样就可以约束了。
逆向互补的思想在很多题目当中都很适用。
