[$\Large\color{#FFBBFF}\textit{Tian-Xing's blog}$](https://Tian-Xing.github.io)
------------
# Description
[传送门](https://www.luogu.com.cn/problem/P4311)
------------
# Solution
首先如果士兵只能给一行或一列造成贡献的答案是$\sum_{i = 1}^m l_i + \sum_{i = 1}^n c_i$。
但是发现有的士兵可以同时给一列和一行造成贡献。
那就算出这些士兵的个数就行了。
$S$向每一行连容量为$l_i$的有向边；每一列向$T$连容量为$c_i$的有向边。
如果坐标$(i,j)$不是障碍，那么第$i$行向第$j$列连容量为$1$的有向边。
跑出来的最大流就是贡献为$2$的士兵数量。
------------
# Code
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 999999999;
const int N = 10050;
const int M = 200050;
int n, m, s, t, head[N], num = 1, dis[N], k, l[150], c[150], p[150][150], sum[500], ans;
struct Node
{
int next, to, dis;
} edge[M * 2];
void Addedge(int u, int v, int w)
{
edge[++num]= (Node){head[u], v, w};
head[u] = num;
}
template <class T>
void Read(T &x)
{
x = 0; int p = 0; char st = getchar();
while (st < '0' || st > '9') p = (st == '-'), st = getchar();
while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
x = p ? -x : x;
return;
}
template <class T>
void Put(T x)
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) Put(x / 10);
putchar(x % 10 + '0');
return;
}
bool Bfs()
{
queue<int> q;
for (int i = 0; i <= t; i++) dis[i] = 0;
dis[s] = 1; q.push(s);
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i = head[u]; i; i = edge[i].next)
if (!dis[edge[i].to] && edge[i].dis)
{
dis[edge[i].to] = dis[u] + 1;
q.push(edge[i].to);
if (edge[i].to == t) return 1;
}
}
return 0;
}
int Dinic(int x, int flow)
{
if (x == t || !flow) return flow;
int rest = flow;
for (int i = head[x]; i && rest; i = edge[i].next)
if (edge[i].dis && dis[edge[i].to] == dis[x] + 1)
{
int v = edge[i].to;
int tmp = Dinic(v, min(flow, edge[i].dis));
rest -= tmp;
edge[i].dis -= tmp;
edge[i ^ 1].dis += tmp;
if (!tmp) dis[v] = 0;
}
return flow - rest;
}
void Add(int u, int v, int w)
{
Addedge(u, v, w);
Addedge(v, u, 0);
return;
}
int Maxflow()
{
int maxflow = 0, tmp;
while (Bfs())
{
tmp = Dinic(s, INF);
if (tmp) maxflow += tmp;
}
return maxflow;
}
int main()
{
Read(m); Read(n); Read(k);
for (int i = 1; i <= m; i++) Read(l[i]), ans += l[i];
for (int i = 1; i <= n; i++) Read(c[i]), ans += c[i];
int x, y;
for (int i = 1; i <= k; i++) Read(x), Read(y), p[x][y] = 1;
s = 0, t = n + m + 1;
for (int i = 1; i <= m; i++) Add(s, i, l[i]);
for (int i = 1; i <= n; i++) Add(i + m, t, c[i]);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
if (!p[i][j])
Add(i, j + m, 1);
sum[i] = sum[i] + !p[i][j];
sum[j + m] = sum[j + m] + !p[i][j];
}
for (int i = 1; i <= m; i++) if (sum[i] < l[i]) { puts("JIONG!"); return 0; }
for (int j = 1; j <= n; j++) if (sum[j + m] < c[j]) { puts("JIONG!"); return 0; }
Put(ans - Maxflow());
return 0;
}
```