首先在所有点上放上士兵，如果初始不合法直接输出，否则考虑删除士兵。
对于每一个士兵，向所在行和所在列连边，每一行/列向汇点流最多能删掉多少个士兵，源点向每一个士兵流1的边，最后最大流即删掉的士兵。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 205 4 #define ll long long 5 #define inf 0x3f3f3f3f 6 struct ji{ 7 int nex,to,len; 8 }edge[N*N]; 9 queue<int>q; 10 int E,n,m,k,x,y,a[N],b[N],d[N],head[N],work[N],vis[N][N]; 11 void add(int x,int y,int z){ 12 edge[E].nex=head[x]; 13 edge[E].to=y; 14 edge[E].len=z; 15 head[x]=E++; 16 if (E&1)add(y,x,0); 17 } 18 bool bfs(){ 19 q.push(0); 20 memset(d,-1,sizeof(d)); 21 d[0]=0; 22 while (!q.empty()){ 23 int k=q.front(); 24 q.pop(); 25 for(int i=head[k];i!=-1;i=edge[i].nex) 26 if ((edge[i].len)&&(d[edge[i].to]<0)){ 27 d[edge[i].to]=d[k]+1; 28 q.push(edge[i].to); 29 } 30 } 31 return d[n+m+1]>=0; 32 } 33 int dfs(int k,int s){ 34 if (k==n+m+1)return s; 35 int p; 36 for(int &i=work[k];i!=-1;i=edge[i].nex) 37 if ((edge[i].len)&&(d[edge[i].to]==d[k]+1)){ 38 p=dfs(edge[i].to,min(s,edge[i].len)); 39 if (p){ 40 edge[i].len-=p; 41 edge[i^1].len+=p; 42 return p; 43 } 44 } 45 return 0; 46 } 47 int dinic(){ 48 int k,ans=0; 49 while (bfs()){ 50 memcpy(work,head,sizeof(work)); 51 while (k=dfs(0,inf))ans+=k; 52 } 53 return ans; 54 } 55 int main(){ 56 scanf("%d%d%d",&n,&m,&k); 57 memset(head,-1,sizeof(head)); 58 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 59 for(int i=1;i<=m;i++)scanf("%d",&b[i]); 60 for(int i=1;i<=k;i++){ 61 scanf("%d%d",&x,&y); 62 if ((++a[x]>m)||(++b[y]>n)){ 63 printf("JIONG!"); 64 return 0; 65 } 66 vis[x][y]=1; 67 } 68 for(int i=1;i<=n;i++)add(0,i,m-a[i]); 69 for(int i=1;i<=n;i++) 70 for(int j=1;j<=m;j++) 71 if (!vis[i][j])add(i,j+n,1); 72 for(int i=1;i<=m;i++)add(i+n,n+m+1,n-b[i]); 73 printf("%d",n*m-k-dinic()); 74 }