Description
有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。 第二行有M个数表示Li。 第三行有N个数表示Ci。 接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。
Output
输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)
4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3
Sample Output
4
数据范围
M, N <= 100, 0 <= K <= M * N
分析
GDKOI前复习一波网络流模板 要把问题转换成先把所有格子都填满，然后再求最多能删掉多少个士兵。 用numl[i]表示第i行可以放多少个士兵，numc[i]表示第i列能放多少个士兵。 那么s向每行连流量为numl[i]-L[i]的边，每列向t连流量为numc[i]-c[i]的边，若第i行第j列不是障碍物则在第i行第j列连流量为1的边，跑一边最大流，然后ans=n*m-k-maxflow
代码
#include <bits/stdc++.h>#define N 305#define INF 0x7fffffusing namespace std;struct NOTE{ int to,next,c,op;}e[N*1000];int cnt,next[N];int c[N],l[N];int numl[N],numc[N];int dis[N],cur[N];int Map[N][N];int n,m,k;int s,t;int ans;void add(int x,int y,int c){ e[++cnt].to = y; e[cnt].next = next[x]; e[cnt].c = c; e[cnt].op = cnt+1; next[x] = cnt; e[++cnt].to = x; e[cnt].next = next[y]; e[cnt].c = 0; e[cnt].op = cnt-1; next[y] = cnt;}bool bfs(){ queue<int> Q; for (int i = s; i <= t; i++) { dis[i] = 0; } dis[s] = 1; Q.push(s); while (!Q.empty()) { int v = Q.front(); Q.pop(); for (int i = next[v]; i; i = e[i].next) { if (e[i].c && !dis[e[i].to]) { int now = e[i].to; dis[now] = dis[v] + 1; Q.push(now); if (e[i].to == t) return 1; } } } return 0;}int dfs(int x,int maxf){ if (x == t || maxf == 0) return maxf; int ret = 0; for (int &i = cur[x]; i; i = e[i].next) { if(e[i].c && dis[e[i].to] == dis[x] + 1) { int f = dfs(e[i].to,min(maxf - ret,e[i].c)); ret += f; e[i].c -= f; e[e[i].op].c += f; if (ret == maxf) break; } } return ret;}void dinic(){ while (bfs()) { for (int i = s; i <= t; i++) cur[i] = next[i]; ans += dfs(s,INF); }}int main(){ scanf("%d%d%d",&n,&m,&k); for (int i = 1; i <= n; i++) { scanf("%d",&l[i]); numl[i]=m; } for (int i = 1; i <= m; i++) { scanf("%d",&c[i]); numc[i] = n; } for(int i = 1; i <= k; i++) { int x,y; scanf("%d%d",&x,&y); Map[x][y] = 1; numl[x]--; numc[y]--; } s = 0; t = n + m + 1; for (int i = 1; i <= n; i++) { if (numl[i] < l[i]) { PRintf("JIONG!/n"); return 0; } add(s,i,numl[i] - l[i]); } for (int i = 1; i <= m; i++) { if (numc[i] < c[i]) { printf("JIONG!/n"); return 0; } add(n+i,t,numc[i] - c[i]); } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (!Map[i][j]) add(i,j+n,1); } dinic(); printf("%d/n",n * m - k - ans);}
