题目链接：https://www.luogu.org/problemnew/show/P4311
知识点： 最大流
解题思路：
对于每一行，建立一条从源点到该行的边，容量为这一行能不放置士兵的点数；
对于每一列，建立一条从该列到汇点的边，容量为这一列能不放置士兵的点数；
对于每一个没有障碍的点 \((x,y)\)，建立一条从第 \(x\) 行到第 \(y\) 列的边，容量为 \(1\)。
从源点到汇点的最大流即为图上可以不放置士兵的最大点数，答案即为图上可以放置士兵的点数减去最大流。
AC代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 const int maxn=110; 5 int L[maxn],C[maxn]; 6 bool zhang[maxn][maxn]; 7 8 const int MAXN = 510;//点数的最大值 9 const int MAXM = 15000;//边数的最大值 10 const int INF = 0x3f3f3f3f; 11 struct Edge{ 12 int to,next,cap,flow; 13 }edge[MAXM];//注意是MAXM 14 int tol; 15 int head[MAXN]; 16 int gap[MAXN],dep[MAXN],cur[MAXN]; 17 void init(){ 18 tol = 0; 19 memset(head,-1,sizeof(head)); 20 } 21 void addedge(int u,int v,int w,int rw = 0){ 22 edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0; 23 edge[tol].next = head[u]; head[u] = tol++; 24 edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0; 25 edge[tol].next = head[v]; head[v] = tol++; 26 } 27 int Q[MAXN]; 28 void BFS(int start,int end){ 29 memset(dep,-1,sizeof(dep)); 30 memset(gap,0,sizeof(gap)); 31 gap[0] = 1; 32 int front = 0, rear = 0; 33 dep[end] = 0; 34 Q[rear++] = end; 35 while(front != rear){ 36 int u = Q[front++]; 37 for(int i = head[u]; i != -1; i = edge[i].next){ 38 int v = edge[i].to; 39 if(dep[v] != -1) 40 continue; 41 Q[rear++] = v; 42 dep[v] = dep[u] + 1; 43 gap[dep[v]]++; 44 } 45 } 46 } 47 int S[MAXN]; 48 int sap(int start,int end,int N){ 49 BFS(start,end); 50 memcpy(cur,head,sizeof(head)); 51 int top = 0; 52 int u = start; 53 int ans = 0; 54 while(dep[start] < N){ 55 if(u == end){ 56 int Min = INF; 57 int inser; 58 for(int i = 0;i < top;i++) 59 if(Min > edge[S[i]].cap - edge[S[i]].flow){ 60 Min = edge[S[i]].cap - edge[S[i]].flow; 61 inser = i; 62 } 63 for(int i = 0;i < top;i++){ 64 edge[S[i]].flow += Min; 65 edge[S[i]^1].flow -= Min; 66 } 67 ans += Min; 68 top = inser; 69 u = edge[S[top]^1].to; 70 continue; 71 } 72 bool flag = false; 73 int v; 74 for(int i = cur[u]; i != -1; i = edge[i].next){ 75 v = edge[i].to; 76 if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){ 77 flag = true; 78 cur[u] = i; 79 break; 80 } 81 } 82 if(flag){ 83 S[top++] = cur[u]; 84 u = v; 85 continue; 86 } 87 int Min = N; 88 for(int i = head[u]; i != -1; i = edge[i].next) 89 if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){ 90 Min = dep[edge[i].to]; 91 cur[u] = i; 92 } 93 gap[dep[u]]--; 94 if(!gap[dep[u]]) 95 return ans; 96 dep[u] = Min + 1; 97 gap[dep[u]]++; 98 if(u != start) 99 u = edge[S[--top]^1].to; 100 } 101 return ans; 102 } 103 int lie[110],han[110]; 104 int main(){ 105 int M,N,K; 106 scanf("%d%d%d",&N,&M,&K); 107 int s=0,t=MAXN-1; 108 init(); 109 for(int i=1;i<=N;i++){ 110 scanf("%d",&L[i]); 111 // addedge(s,i,L[i]); 112 han[i]=M; 113 } 114 for(int i=1;i<=M;i++){ 115 scanf("%d",&C[i]); 116 // addedge(i+N,t,C[i]); 117 lie[i]=N; 118 } 119 int sum=N*M; 120 for(int i=0;i<K;i++){ 121 int x,y; 122 scanf("%d%d",&x,&y); 123 zhang[x][y]=true; 124 sum--; 125 lie[y]--,han[x]--; 126 } 127 for(int i=1;i<=M;i++){ 128 if(lie[i]<C[i]){ 129 printf("JIONG!\n"); 130 return 0; 131 } 132 addedge(i+N,t,lie[i]-C[i]); 133 } 134 for(int i=1;i<=N;i++){ 135 if(han[i]<L[i]){ 136 printf("JIONG!\n"); 137 return 0; 138 } 139 addedge(s,i,han[i]-L[i]); 140 }//特判 "JIONG" 的情况 141 142 for(int i=1;i<=N;i++){ 143 for(int j=1;j<=M;j++){ 144 if(!zhang[i][j]) 145 addedge(i,j+N,1); 146 } 147 } 148 int saps=sap(s,t,N+M+2); 149 printf("%d\n",sum-saps); 150 return 0; 151 }