士兵占领

士兵占领

Time Limit:10000MS  Memory Limit:65536K
Total Submit:48 Accepted:32
Case Time Limit:1000MS

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

Source

哎。。我太SB了。。这题我问了glassices神牛才知道怎么做。。神牛真是太强大了!!
Orz!!!!!
恩。。我一看到这个题目。。第一反应就是网络流。。然后立马感觉到Li和Ci就是所谓的下届,
然后想到上下界网络最小流囧。。。
感觉非常繁琐啊。。然后神牛告诉我说要转化一下。。
先把棋盘放满,如果不能满足就囧了。。
然后可以发现每个行和列能拿掉的最大值就知道了。。
然后最少数=全部数-最多能拿掉几个。。
就成最大流了囧。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxv=200+10,maxn=100;
using namespace std;
int vs,vt,n,m,k,v,ans=0;
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[maxv]={};
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
bool M[maxn][maxn]={};
int L[maxn],C[maxn];
void Fail()
{
puts("JIONG!");
exit(0);
}
void Init()
{
cin>>n>>m>>k;v=n+m;vs=v++;vt=v++;
rep(i,n)cin>>L[i];
rep(i,m)cin>>C[i];
int x,y;
rep(i,k)
{
scanf("%d%d",&x,&y);–x;–y;
M[x][y]=true;
}
rep(i,n)rep(j,m)if(!M[i][j])L[i]–,C[j]–,ans++;
rep(i,n)if(L[i]>0)Fail();
rep(i,m)if(C[i]>0)Fail();
}
void BuildGraph()
{
rep(i,n)AddEdge(vs,i,-L[i]);
rep(j,m)AddEdge(j+n,vt,-C[j]);
rep(i,n)rep(j,m)if(!M[i][j])
AddEdge(i,j+n,1);
}
bool vis[maxv]={};
int dfs(int no,int m)
{
if(no==vt)return m;
vis[no]=true;
for(Edge*e=E[no];e;e=e->next)if(!vis[e->t]&&e->c)
if(int d=dfs(e->t,min(m,e->c)))
return e->c-=d,e->op->c+=d,d;
return 0;
}
int CalFlow()
{
int flow=0;
do
{
memset(vis,0,sizeof vis);
int d=dfs(vs,inf);
if(d)flow+=d;
else break;
}while(1);
return flow;
}
int main()
{
//freopen("in","r",stdin);
Init();
BuildGraph();
cout<<ans-CalFlow()<<endl;
}

2 thoughts on “士兵占领

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>