士兵占领

题目描述

有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

输入格式
第一行两个数M, N, K分别表示棋盘的行数，列数以及士兵的个数。 第二行有M个数表示Li。 第三行有N个数表示Ci。 接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。

输出格式
输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)

输入输出样例

输入
4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3

输出
4

这道题做法挺多的，我就说一下我的网络流做法吧。

这道题只用最大流就可以解决了，我们从题目可以想到，每个士兵会有两种情况，贡献度为1和贡献度为2，所以我们要尽可能的要贡献度为2的士兵，这样我们用需要的总的贡献度为1的士兵，减去贡献度为2的士兵，即为答案。

现在问题就变成了，怎么去找到最多贡献度为2的士兵？

做过几道网络流的小伙伴们不难想到，考虑建图:

每行建立一个点Ai，与源点S相连，容量是ri，每列建一个点Bj与汇点T相连，容量是cj 。
若当前点可以放士兵，则在Ai与Bj之间连一条容量为1的边。
这样建图的最大流就是贡献度为2的士兵最大数量，既保证了一个格子最多一个士兵也保证了不会有多余的士兵。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=10010;	
int n,m,k,l[N<<1],c[N<<1],flag,numx[N<<1],numy[N<<1],g[N<<1][N<<1],s,t,cnt;
int head[N<<4],nex[M<<4],w[M<<4],to[M<<4],tot=1;
void add(int a,int b,int c){
	w[++tot]=c; to[tot]=b; nex[tot]=head[a]; head[a]=tot;
}
struct node{
	int v,e;
}p[N<<4];
bool bfs(){
	int vis[N<<4]={0};	queue<int> q;
	q.push(s);	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!vis[to[i]]){
				p[to[i]].v=u; p[to[i]].e=i;
				vis[to[i]]=1;	q.push(to[i]);
				if(to[i]==t)	return true;
			}
		}
	}
	return false;
}
int EK(){
	int res=0;
	while(bfs()){
		int mi=0x3f3f3f3f;
		for(int i=t;i!=s;i=p[i].v)	mi=min(mi,w[p[i].e]);
		for(int i=t;i!=s;i=p[i].v){
			w[p[i].e]-=mi;	w[p[i].e^1]+=mi;
		}
		res+=mi;
	}
	return res;
}
int main(){
	cin>>n>>m>>k;	s=6*N,t=6*N+1;
	for(int i=1;i<=n;i++){
		cin>>l[i];	if(!l[i])	continue;
		cnt+=l[i],add(s,i,l[i]),add(i,s,0);
	}	
	for(int i=1;i<=m;i++){
		cin>>c[i];	if(!c[i])	continue;
		cnt+=c[i],add(i+2*N,t,c[i]),add(t,i+2*N,0);
	}	
	while(k--&&!flag){
		int x,y;	cin>>x>>y;	numx[x]++;	numy[y]++;	g[x][y]=1;
		if(l[x]+numx[x]>n||c[y]+numy[y]>m)	flag++;
	}
	if(flag){
		puts("JIONG!");	return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!g[i][j]){
				add(i,j+2*N,1);	add(j+2*N,i,0);
			}
		}
	}
	cout<<cnt-EK()<<endl;
	return 0;
}//每行建立一个点Ai，与源点S相连，容量是ri，每列建一个点Bj与汇点T相连，容量是cj