1458: 士兵占领
Time Limit: 10 Sec Memory Limit: 64 MB Submit: 632 Solved: 366 [Submit][Status][Discuss] Description
有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
Input
第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。 第二行有M个数表示Li。 第三行有N个数表示Ci。 接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。
Output
输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，，输出”JIONG!” (不含引号)
Sample Input
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
有源汇有上下界的最小流。
详见《有上下界的网络流问题》
;struct edge{int from,to,cap,flow,ne;}E[M];int tot,h[M],d[M],s,t,cur[M],cant[105][105],v[M],n,m;void Addedge(int from,int to,int cap){E[++tot]=(edge){from,to,cap,0,h[from]};h[from]=tot;E[++tot]=(edge){to,from,0,0,h[to]};h[to]=tot;}int bfs(){for (int i=s;i<=t;i++)v[i]=0;v[s]=1;queue<int> q;q.push(s);d[s]=0;while (!q.empty()){int x=q.front();q.pop();for (int i=h[x];i;i=E[i].ne){edge e=E[i];if (!v[e.to]&&e.cap>e.flow){v[e.to]=1;d[e.to]=d[x]+1;q.push(e.to);}}}return v[t];}int dfs(int x,int a){if (x==t||!a) return a;int flow=0;for (int &i=cur[x];i;i=E[i].ne){edge &e=E[i];if (d[e.to]!=d[x]+1) continue;int f=dfs(e.to,min(a,e.cap-e.flow));if (f>0){flow+=f;a-=f;e.flow+=f;E[i^1].flow-=f;if (!a) break;}}return flow;}int dinic(){int flow=0;while (bfs()){for (int i=s;i<=t;i++)cur[i]=h[i];flow+=dfs(s,inf);}return flow;}int main(){tot=1;int k;scanf(“%d%d%d”,&n,&m,&k);int jud=0;int s1=n+m+1,t1=n+m+2;s=0,t=n+m+3;for (int i=1;i<=n;i++){int x;scanf(“%d”,&x);jud+=x;Addedge(s1,i,m-x);Addedge(s,i,x),Addedge(s1,t,x);}for (int i=1;i<=m;i++){int x;scanf(“%d”,&x);Addedge(i+n,t1,n-x);Addedge(s,t1,x),Addedge(i+n,t,x);}for (int i=1;i<=k;i++){int x,y;scanf(“%d%d”,&x,&y);cant[x][y]=1;}for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (!cant[i][j])Addedge(i,n+j,1);int flow=dinic();if (flow==jud){Addedge(t1,s1,inf);flow-=dinic();printf(“%d\n”,E[tot-1].flow);}else puts(“JIONG!”);return 0;}
世上最累人的事，莫过於虚伪的过日子
