Description

有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
Input

第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。 第二行有M个数表示Li。 第三行有N个数表示Ci。 接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。
Output

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)
Sample Input
4 4 4

1 1 1 1

0 1 0 3

1 4

2 2

3 3

4 3

Sample Output
4

数据范围

M, N <= 100, 0 <= K <= M * N

解法：考虑一下最大流建边是考虑边的容量上限，这里给的是下限，如果我们反面考虑就可以转化成最大流

了。把行列分别当成点，那么源点向行的点连容量为m-x-l[i]，x表示第i行的坏点的个数。同理，汇点向汇点

连n-x-c[i]的点，x为第i列坏点的个数。对于原图中的每一个好点，连边，跑最大流。最后答案就是所有的好点

的个数减去最大流。

///BZOJ 1457 #include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
const int maxm = 100010;
const int inf = 0x3f3f3f3f;

struct G
{
    int v, cap, next;
    G() {}
    G(int v, int cap, int next) : v(v), cap(cap), next(next) {}
} E[maxm];
int p[maxn], T;
int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化，qw队列
void init()
{
    memset(p, -1, sizeof(p));
    T = 0;
}
void add(int u, int v, int cap)
{
    E[T] = G(v, cap, p[u]);
    p[u] = T++;
    E[T] = G(u, 0, p[v]);
    p[v] = T++;
}
bool bfs(int st, int en, int n)
{
    int i, u, v, head, tail;
    for(i = 0; i <= n; i++) d[i] = -1;
    head = tail = 0;
    d[st] = 0;
    qw[tail] = st;
    while(head <= tail)
    {
        u = qw[head++];
        for(i = p[u]; i + 1; i = E[i].next)
        {
            v = E[i].v;
            if(d[v] == -1 && E[i].cap > 0)
            {
                d[v] = d[u] + 1;
                qw[++tail] = v;
            }
        }
    }
    return (d[en] != -1);
}
int dfs(int u, int en, int f)
{
    if(u == en || f == 0) return f;
    int flow = 0, temp;
    for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next)
    {
        G& e = E[temp_p[u]];
        if(d[u] + 1 == d[e.v])
        {
            temp = dfs(e.v, en, min(f, e.cap));
            if(temp > 0)
            {
                e.cap -= temp;
                E[temp_p[u] ^ 1].cap += temp;
                flow += temp;
                f -= temp;
                if(f == 0)  break;
            }
        }
    }
    return flow;
}
int dinic(int st, int en, int n)
{
    int i, ans = 0;
    while(bfs(st, en, n))
    {
        for(i = 0; i <= n; i++) temp_p[i] = p[i];
        ans += dfs(st, en, inf);
    }
    return ans;
}
int l[maxn], c[maxn], mp[maxn][maxn];
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n,&m,&k);
    for(int i=1; i<=n; i++) scanf("%d", &l[i]);
    for(int i=1; i<=m; i++) scanf("%d", &c[i]);
    int source = n+m+1, sink = source+1;
    for(int i=1; i<=k; i++)
    {
        int x, y;
        scanf("%d%d", &x,&y);
        mp[x][y] = 1;
    }
    int flag = 0;
    for(int i=1; i<=n; i++)
    {
        int t = 0;
        for(int j=1; j<=m; j++)
        {
            t+=mp[i][j];
        }
        if(l[i]>m-t)
        {
            flag=1;
        }
        else
        {
            flag = 0;
        }
    }
    for(int i=1; i<=m; i++)
    {
        int t = 0;
        for(int j=1; j<=n; j++)
        {
            t+=mp[j][i];
        }
        if(c[i]>n-t)
        {
            flag = 1;
        }
        else
        {
            flag = 0;
        }
    }
    if(flag)
    {
        printf("JIONG!\n");
    }
    else
    {
        init();
        int sum = 0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                sum+=!mp[i][j];
            }
        }
        //cout<<sum<<endl;
        for(int i=1; i<=n; i++)
        {
            int t = 0;
            for(int j=1; j<=m; j++)
            {
                t+=mp[i][j];
            }
            int x=m-t-l[i];
            add(source, i, x);
        }
        for(int i=1; i<=m; i++){
            int t=0;
            for(int j=1; j<=n; j++){
                t+=mp[j][i];
            }
            int x=n-t-c[i];
            add(i+n, sink, x);
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(mp[i][j]) continue;
                add(i, j+n, 1);
            }
        }
        int ans = sum - dinic(source, sink, sink+1);
        printf("%d\n", ans);
    }
    return 0;
}