摆棋子（chessman）

有源汇上下界可行流。。。。 S___B（题目）

大哥讲过原题QAQ

把行和列都看作一个点；

按题目要求连边就可以了

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
/*
名利真吾事，纷然过眼休。人生能有死，天道未曾修
百战身皆朽，群心志已酬。一场无限业，何处可优游
*/
const int N = 1e6 + 1000,inf = 1e9;
int tot = 1,n,m,K,maxflow;
int sum,ans,st,en,ss,ee;
int dep[N],head[N];
int vis[110][110],e[N];
queue<int> q;
struct node{int nex,to,val;} a[N << 2];
void add(int f,int t,int v)
{
    a[++ tot].nex = head[f];
    a[tot].to = t;
    a[tot].val = v;
    head[f] = tot;
}
int bfs(int x,int y)
{
    while(!q.empty()) q.pop();
    memset(dep,0,sizeof(dep));
    dep[x] = 1; q.push(x); 
    while(!q.empty())
    {
        int f = q.front(); q.pop();
        for(int i = head[f],to;i;i = a[i].nex)
        {
            to = a[i].to;
            if(dep[to] || !a[i].val) continue;
            dep[to] = dep[f] + 1;
            if(to == y) return 1;
            q.push(to); 
        }
    }
    return 0;
}

int dfs(int now,int flow,int tt)
{
    if(now == tt || !flow) return flow;
    int res = flow,k;
    for(int i = head[now],to;i && res;i = a[i].nex)
    {
        to = a[i].to;
        if(a[i].val && dep[to] == dep[now] + 1)
        {
            k = dfs(to,min(res,a[i].val),tt);
            if(!k) {dep[to] = -1; continue;}
            a[i].val -= k; a[i ^ 1].val += k;
            res -= k;
        }
    }
    return flow - res;
}

void dinic(int x,int y)
{
    int flow = 0;
    maxflow = 0;
    while(bfs(x,y)) while(flow = dfs(x,inf,y)) maxflow += flow;
}

void init()
{
    n = read(); m = read(); K = read();
    st = n + m + 1; en = n + m + 2; ss = n + m + 3; ee = n + m + 4;
    for(int i = 1,x;i <= n;i ++)
    {
        x = read();
        e[st] -= x; e[i] += x;
        add(st,i,inf); add(i,st,0);
    }
    for(int i = 1,x;i <= m;i ++)
    {
        x = read();
        e[en] += x; e[i + n] -= x;
        add(i + n,en,inf); add(en,i + n,0);
    }
    for(int i = 1,x,y;i <= K;i ++)
    {
        x = read(); y = read();
        vis[x][y] = 1;
    }
}

int main()
{
    freopen("chessman.in","r",stdin);
    freopen("chessman.out","w",stdout);
    init(); 
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            if(vis[i][j]) continue;
            add(i,j + n,1); add(j + n,i,0); 
        }
    }

    for(int i = 1;i <= n + m + 2;i ++)
    {
        if(e[i] > 0) {add(ss,i,e[i]); add(i,ss,0); sum += e[i];}
        else if(e[i] < 0) {add(i,ee,-e[i]); add(ee,i,0);}
    }
    add(en,st,inf); add(st,en,0); dinic(ss,ee);
    if(maxflow != sum) {puts("No Solution"); return 0;}
    ans = a[head[st]].val; head[en] = a[head[en]].nex; head[st] = a[head[st]].nex;
    dinic(en,st);
    printf("%d\n",ans - maxflow);
    fclose(stdin);fclose(stdout);
    return 0;
}
/*
4 4 4
1 1 1 1
1 1 1 3
1 4
2 2
3 3
4 3
*/