[补档]士兵占领

士兵占领

题目

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1458

有一个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

OUTPUT

4

解题报告

也是很裸的网络流，所有行与源点连边，容量为Li，所有列与汇点连边，容量为Ci，可以放士兵的格子对应的行和列连边，跑最大流即为答案

要注意的是：点的坐标与数组大小的问题

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<queue>
  5 using namespace std;
  6 inline int read(){
  7     int sum(0);
  8     char ch(getchar());
  9     for(;ch<'0'||ch>'9';ch=getchar());
 10     for(;ch>='0'&&ch<='9';sum=sum*10+ch-'0',ch=getchar());
 11     return sum;
 12 }
 13 struct edge{
 14     int s,e,w,n;
 15 }a[50001];
 16 int pre[250],tot;
 17 inline void insert(int s,int e,int w){
 18     a[tot].s=s;
 19     a[tot].e=e;
 20     a[tot].w=w;
 21     a[tot].n=pre[s];
 22     pre[s]=tot++;
 23 }
 24 int n,m,k;
 25 int sup;
 26 int l[101],c[101];
 27 bool g[101][101];
 28 int sum(0);
 29 int dis[301];
 30 inline bool bfs(int s,int t){
 31     memset(dis,0,sizeof(dis));
 32     queue<int>q;
 33     q.push(s);
 34     dis[s]=1;
 35     while(!q.empty()){
 36         int k(q.front());
 37         q.pop();
 38          for(int i=pre[k];i!=-1;i=a[i].n){
 39             if(!a[i].w||dis[a[i].e])
 40                 continue;
 41             dis[a[i].e]=dis[k]+1;
 42             if(a[i].e==t)
 43                 return true;
 44             q.push(a[i].e);
 45         }
 46     }
 47     return false;
 48 }
 49 inline int my_min(int a,int b){
 50     return a<b?a:b;
 51 }
 52 inline int dfs(int now,int flow){
 53     if(now==sup)
 54         return flow;
 55     int tmp(flow),f;
 56     for(int i=pre[now];i!=-1;i=a[i].n){
 57         if(!a[i].w||!tmp||dis[a[i].e]!=dis[now]+1)
 58             continue;
 59         f=dfs(a[i].e,my_min(a[i].w,tmp));
 60         if(!f){
 61             dis[a[i].e]=0;
 62             continue;
 63         }
 64         a[i].w-=f;
 65         a[i^1].w+=f;
 66         tmp-=f;
 67     }
 68     return flow-tmp;
 69 }
 70 inline bool judge(){
 71     int tmp;
 72     for(int i=1;i<=m;i++){
 73         tmp=0;
 74         for(int j=1;j<=n;j++)
 75             if(g[i][j])
 76                 tmp++;
 77         if(tmp<l[i])
 78             return true;
 79     }
 80     for(int j=1;j<=n;j++){
 81         tmp=0;
 82         for(int i=1;i<=m;i++)
 83             if(g[i][j])
 84                 tmp++;
 85         if(tmp<c[j])
 86             return true;
 87     }
 88     return false;
 89 }
 90 int ans(0),inf(0x7fffffff);
 91 int main(){
 92     memset(pre,-1,sizeof(pre));
 93     memset(g,true,sizeof(g));
 94     m=read(),n=read(),k=read();
 95     sup=n+m+1;
 96     for(int i=1;i<=m;i++)
 97         l[i]=read(),sum+=l[i];
 98     for(int i=1;i<=n;i++)
 99         c[i]=read(),sum+=c[i];
100     for(int i=1;i<=k;i++){
101         int x(read()),y(read());
102         g[x][y]=0;
103     }
104     if(judge()){
105         puts("JIONG!");
106         return 0;
107     }
108     for(int i=1;i<=m;i++)
109         for(int j=1;j<=n;j++)
110             if(g[i][j])
111                 insert(i,j+m,1),insert(j+m,i,0);
112     for(int i=1;i<=m;i++)
113         insert(0,i,l[i]),insert(i,0,0);
114     for(int i=1;i<=n;i++)
115         insert(i+m,sup,c[i]),insert(sup,i+m,0);
116     while(bfs(0,sup))
117         ans+=dfs(0,inf);
118     printf("%d",sum-ans);
119     return 0;
120 }

View Code