Title Description
There is a checkerboard for M * N, some of which are obstacles. Now you have to choose some grid to place some soldiers, a grid can place up to one soldier, obstacle grid can not place soldiers. We call these soldiers occupying the whole chessboard. When they meet the requirements of line I, at least Li soldiers are placed, column J.At least Cj soldiers were placed. Now your task is to require the use of a minimum number of soldiers to occupy the whole chessboard.
Input output format
Input format:
The first row, the two numbers M, N and K, respectively indicate the number of rows, the number of columns, and the number of soldiers. The second row has M numbers to represent Li. The third row has N numbers to represent Ci. Next, there are K rows, each row has two numbers X, and Y means (X, Y) the grid is an obstacle.
Output format:
Output a number to indicate the minimum number of soldiers to use. If no matter how many soldiers you put on the board can’t occupy the entire board, output “JIONG!” (without quotes)
Examples of input and output
4 4 4 1 1 1 1 0 1 0 3 1 4 2 2 3 3 4 3
4
Explain
M, N <= 100, 0 <= K <= M * N Local
An explanation
It is said that positive solutions are upper and lower network flows. Can we also run the cost flow? But the maximum flow can also be?
Here is the maximum flow method.
We can put chessmen in all places where we can put them, and then see how many pieces we can take.
Create a point for each column in each row, and if $(x, y) $is not a barrier, edge the point corresponding to $(x, y) $to the point corresponding to $(y) $, with a capacity of $1 $, indicating that the point can be deleted once
Then, from the source point to the edge of all rows, the capacity is the maximum number of soldiers that can be deleted from this row (total grid number – obstacle grid number – must grid number)
From all the columns to the sink point, the capacity is the maximum number of soldiers that can be deleted in this column (ibid.)
In this way, it can be found that no matter how to delete, it will not exceed the restrictions. Then delete the most soldiers, just run the maximum flow.
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 inline int read(){ 11 #define num ch-'0' 12 char ch;bool flag=0;int res; 13 while(!isdigit(ch=getc())) 14 (ch=='-')&&(flag=true); 15 for(res=num;isdigit(ch=getc());res=res*10+num); 16 (flag)&&(res=-res); 17 #undef num 18 return res; 19 } 20 const int N=205,M=50005; 21 int head[N],Next[M],ver[M],edge[M],tot=1; 22 int dep[N],cur[N],l[N],c[N],ll[N],cc[N],vis[N][N],n,m,k,s,t,ans; 23 queue<int> q; 24 inline void add(int u,int v,int e){ 25 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 26 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=0; 27 } 28 bool bfs(){ 29 memset(dep,-1,sizeof(dep)); 30 while(!q.empty()) q.pop(); 31 for(int i=s;i<=t;++i) cur[i]=head[i]; 32 q.push(s),dep[s]=0; 33 while(!q.empty()){ 34 int u=q.front();q.pop(); 35 for(int i=head[u];i;i=Next[i]){ 36 int v=ver[i]; 37 if(dep[v]<0&&edge[i]){ 38 dep[v]=dep[u]+1,q.push(v); 39 if(v==t) return true; 40 } 41 } 42 } 43 return false; 44 } 45 int dfs(int u,int limit){ 46 if(u==t||!limit) return limit; 47 int flow=0,f; 48 for(int i=head[u];i;i=Next[i]){ 49 int v=ver[i]; 50 if(dep[v]==dep[u]+1&&(f=dfs(v,min(limit,edge[i])))){ 51 flow+=f,limit-=f; 52 edge[i]-=f,edge[i^1]+=f; 53 if(!limit) break; 54 } 55 } 56 if(!flow) dep[u]=-1; 57 return flow; 58 } 59 int dinic(){ 60 int flow=0; 61 while(bfs()) flow+=dfs(s,inf); 62 return flow; 63 } 64 int main(){ 65 //freopen("testdata.in","r",stdin); 66 n=read(),m=read(),k=read(),ans=n*m; 67 s=0,t=n+m+1; 68 for(int i=1;i<=n;++i) l[i]=read(); 69 for(int i=1;i<=m;++i) c[i]=read(); 70 for(int i=1;i<=k;++i){ 71 int x=read(),y=read();vis[x][y]=1; 72 ++ll[x],++cc[y],--ans; 73 } 74 for(int i=1;i<=n;++i) 75 for(int j=1;j<=m;++j) 76 if(!vis[i][j]) add(i,j+n,1); 77 for(int i=1;i<=n;++i){ 78 int p=m-ll[i]-l[i]; 79 if(p<0) return puts("JIONG!"),0; 80 add(s,i,p); 81 } 82 for(int i=1;i<=m;++i){ 83 int p=n-cc[i]-c[i]; 84 if(p<0) return puts("JIONG!"),0; 85 add(i+n,t,p); 86 } 87 ans-=dinic(); 88 printf("%d\n",ans); 89 return 0; 90 }