将最少士兵数转化为最多能删多少士兵建图即可。
By：大奕哥
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=3500; 4 int head[N],cnt=-1,l[N],c[N],n,m,k,a[105][105]; 5 struct node{ 6 int to,nex,w; 7 }e[1000005]; 8 void add(int x,int y,int w) 9 { 10 e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;e[cnt].w=w; 11 e[++cnt].to=x;e[cnt].nex=head[y];head[y]=cnt;e[cnt].w=0; 12 } 13 int d[N],v[N],s,t; 14 queue<int>q; 15 bool bfs() 16 { 17 memset(v,0,sizeof(v)); 18 memset(d,-1,sizeof(d)); 19 d[s]=0;q.push(s); 20 while(!q.empty()) 21 { 22 int x=q.front();q.pop();v[x]=1; 23 for(int i=head[x];i!=-1;i=e[i].nex) 24 { 25 int y=e[i].to; 26 if(d[y]!=-1||!e[i].w)continue; 27 d[y]=d[x]+1; 28 if(!v[y]){ 29 q.push(y);v[y]=1; 30 } 31 } 32 } 33 return d[t]!=-1; 34 } 35 int dfs(int x,int w,int yy) 36 { 37 if(!w||x==yy)return w; 38 int s=0; 39 for(int i=head[x];i!=-1;i=e[i].nex) 40 { 41 int y=e[i].to; 42 if(d[y]!=d[x]+1||!e[i].w)continue; 43 int flow=dfs(y,min(e[i].w,w-s),yy); 44 if(!flow)d[y]=-1; 45 e[i].w-=flow;e[i^1].w+=flow;s+=flow; 46 if(s==w)return s; 47 } 48 return s; 49 } 50 int main() 51 { 52 scanf("%d%d%d",&m,&n,&k);memset(head,-1,sizeof(head)); 53 for(int i=1;i<=m;++i)scanf("%d",&l[i]),l[i]=n-l[i]; 54 for(int i=1;i<=n;++i)scanf("%d",&c[i]),c[i]=m-c[i]; 55 for(int i=1;i<=k;++i) 56 { 57 int x,y; 58 scanf("%d%d",&x,&y); 59 a[x][y]=1; 60 l[x]--;c[y]--; 61 } 62 for(int i=1;i<=m;++i) 63 for(int j=1;j<=n;++j) 64 if(!a[i][j]) 65 add(i,j+m,1); 66 s=0;t=n+m+1;int ans=0; 67 for(int i=1;i<=m;++i)add(s,i,l[i]); 68 for(int j=1;j<=n;++j)add(j+m,t,c[j]); 69 while(bfs()){ 70 ans+=dfs(s,1e9,t); 71 } 72 if(!ans)puts("JIONG"); 73 else printf("%d ",n*m-k-ans); 74 return 0; 75 }