【算法】我,网络流,再生产!(一)

(玩了个少剧的梗2333333333333333)被zhhx大爷的课件锤到自闭,瞬间觉得自己学了个假的网络流,好好再整理下课件的题目qwq。
首先是个贪心模拟网络流的题目
BZOJ 3716 [PA2014]Muzeum
这个题首先很显然,是个最大权闭合子图,因为手办对警卫有依赖关系,但是你考虑直接建一个最大权闭合子图显然是不太现实的,因为nm都是2e5这种级别的,网络流就算是再玄学也不可能跑得过去,那么这个时候我们就只能贪心/dp了。
首先我们可以通过向量的伸缩使得这个图变成直角,那么变成直角之后我们是不是就可以扫描线之类的处理了。
提前将伸缩好的手办和警卫按照x从小到大排序,之后用set维护y。
考虑网络流我们需要流动,这个地方我们用类似于流的思想,每次从较高处去拿一个手办(因为显然较低的更普遍适用),用这个手办的值去抵消守卫所收贿赂,直到被抵消完或者没法抵消,那么就完成了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const lo ms = 2e5 + 10;

lo n, m, w, h, lx, ly, lz, ans;

struct node
{
    lo x, y, v;
}a[ms], b[ms];

inline bool cmp(node a, node b)
{
    return a.x < b.x;
}

multiset <pair <lo, lo> > mmp;

multiset <pair <lo, lo> >::iterator it;

int main()
{
    re(n), re(m), re(w), re(h);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), re(lz), lx *= h, ly *= w, a[i] = (node){lx + ly, lx - ly, lz}, ans += lz;
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), re(lz), lx *= h, ly *= w, b[i] = (node){lx + ly, lx - ly, lz};
    sort(a + 1, a + 1 + n, cmp), sort(b + 1, b + 1 + m, cmp);
    int ta = 1;
    for(ri i = 1; i <= m; i ++)
    {
        while(ta <= n && a[ta].x <= b[i].x)
            mmp.insert(make_pair(a[ta].y, a[ta].v)), ta ++;
        it = mmp.lower_bound(make_pair(b[i].y, 0));
        lo rt = b[i].v;
        while(rt && it != mmp.end())
        {
            pair <lo, lo> qaq = *it; mmp.erase(it);
            int x = min(rt, qaq.second);
            rt -= x, ans -= x, qaq.second -= x;
            if(qaq.second)
                mmp.insert(qaq);
            else
                it = mmp.lower_bound(make_pair(b[i].y, 0));
        }
    }
    printf("%lld", ans);
}

luogu P3731 [HAOI2017]新型城市化
这个题目学过了可能会挺套路的。
首先考虑问题转化,题目里面实际上给了我们一张补图,而城市群实际上是个团,最大城市群实际上也就是原图的最大团,那么因为团是两两有边的,所以到了补图上面就是两两不能有边,也就是最大独立集。
而这个补图根据题意可知,是一个二分图,而二分图的最大独立集=所有点-二分图最小覆盖,也挺好理解的,你选择最少的点就可以覆盖整个图,那么最小覆盖剩下的点也一定是坠多的。
我们还需要进行第三次转化,最小覆盖==最大匹配,考虑感性的证明,现在存在一个最大匹配,那么不会存在还能够匹配的两个点,也就说对于每一个边都是存在至少一个点被匹配的,那么一定被覆盖过了;考虑存在一个不是最大匹配但是已经完成覆盖的情况,那么也就说至少还存在两个点可以通过增广路进行匹配,那么也就说还存在没有被完全覆盖的边,不符合初始条件,即不存在。
那么经过这三次转化之后我们就将问题从求最大团到最大匹配了。我们的目的是通过删去这个补图的某些边使得最大团变大,也就说补图的最大独立集变大->最小覆盖减小->最大匹配减小。
那么只要考虑那些边一定在最大匹配就好了,割掉他们就一定会减少最大匹配了。
这个时候就是上套路了,对残量网络求scc,一个边一定在最大匹配当且仅当这个边是满流边且两端不在同一个连通分量里面。感性理解下的话就是如果在一个连通分量,至少存在两种方案可以选择,而不在同一个连通分量里的就没得选择了。

// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 2e5 + 10;

int lx, ly, t, lz, n, m, tot = -1, head[ms], ff[ms], ll[ms], he[ms], col[ms];

int de[ms], dfn[ms], scc[ms], low[ms], sta[ms], ta, cnt, ColNum, pos[ms];

struct in
{
    int to, ne, co;
}ter[ms << 2], e[ms << 2];

inline void build(int f, int l, int c)
{
    e[++ tot] = (in){l, he[f], c}, he[f] = tot;
    e[++ tot] = (in){f, he[l], 0}, he[l] = tot;
}

inline void rebuild(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

queue <int> q;

inline void bfs(int s)
{
    q.push(s), col[s] = 0;
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = he[qaq]; i >= 0; i = e[i].ne)
        {
            int to = e[i].to;
            if(col[to] < 0)
                col[to] = col[qaq] ^ 1, q.push(to);
        }
    }
}

inline bool dinic_bfs()
{
    for(ri i = 1; i <= t; i ++)
        de[i] = 0;
    de[0] = 1, q.push(0);
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(!de[to] && ter[i].co)
                q.push(to), de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            int tmp = dfs(to, min(fl, ter[i].co));
            if(tmp > 0)
            {
                ter[i].co -= tmp, ter[i ^ 1].co += tmp, fl -= tmp, rt += tmp;
                if(!fl)
                    return rt;
            }
        }
    }
    return rt;
}

inline void dinic()
{
    while(dinic_bfs())
        dfs(0, 1e9 + 7);
}

bool flag[ms];

void tarjan(int no, int f)
{
    dfn[no] = low[no] = ++ cnt, sta[++ ta] = no, flag[no] = 1;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if((!ter[i].co) || to == f)
            continue;
        if(!dfn[to])
            tarjan(to, no), low[no] = min(low[no], low[to]);
        else if(flag[to])
            low[no] = min(low[no], dfn[to]);
    }
    if(low[no] == dfn[no])
    {
        ColNum ++;
        while(ta > 0)
        {
            int qaq = sta[ta]; ta --; scc[qaq] = ColNum, flag[qaq] = 0;
            if(qaq == no)
                break;
        }
    }
}

pair <int, int> ans[ms];

inline void solve()
{
    ta = 0;
    for(ri i = 1; i <= m; i ++)
        if((!ter[pos[i]].co) && scc[ff[i]] != scc[ll[i]])
            ans[++ ta] = ff[i] < ll[i] ? make_pair(ff[i], ll[i]) : make_pair(ll[i], ff[i]);
    sort(ans + 1, ans + 1 + ta);
    printf("%d\n", ta);
    for(ri i = 1; i <= ta; i ++)
        printf("%d %d\n", ans[i].first, ans[i].second);
}

int main()
{
    re(n), re(m), t = n + 5;
    memset(head, -1, sizeof(head)), memset(he, -1, sizeof(he)), memset(col, -1, sizeof(col));
    for(ri i = 1; i <= m; i ++)
        re(ff[i]), re(ll[i]), build(ff[i], ll[i], 0);
    for(ri i = 1; i <= n; i ++)
        if(col[i] < 0)
            bfs(i);
    for(ri i = 1; i <= m; pos[i] = tot - 1, i ++)
        if(col[ff[i]])
            rebuild(ll[i], ff[i], 1);
        else
            rebuild(ff[i], ll[i], 1);
    for(ri i = 1; i <= n; i ++)//源点连颜色为0的,汇点;连颜色为1的
        if(col[i])
            rebuild(i, t, 1);
        else
            rebuild(0, i, 1);
    dinic();
    for(ri i = 0; i <= t; i ++)
        if(!dfn[i])
            tarjan(i, 0);
    solve();
}

luogu P3329 [ZJOI2011]最小割
这个题如果学过最小割树那么他就是个模板。原理非常简单,建立一个最小割树,然后枚举每一对,看看它是不是超过限制的大小就好。
关键是怎么建,其实这里不用直接建出来…………
类似于归并的思想,开始先生成一个12345……n这样一个序列,然后类似于归并,处理一整个区间,每次把区间的开头作为源点,结尾作为汇点,跑一下dinic,然后按照与s/t的连通性把这个区间拆分成两半,枚举点对,如果这两个点对不在同一个小区间,就计算答案。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 155;

lo T, n, m, qq, x, tot, lx, ly, lz, ans[ms][ms], pri[ms * ms];

int q[ms], de[ms], a[ms], tmp[ms], head[ms], he[ms];

bool flag[ms];

struct in
{
    int to, ne; lo co;
}ter[10010];

struct node
{
    int pos; lo num, ans;
}Ask[40];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], c}, head[l] = tot;
}

inline bool bfs(int s, int t)
{
    int hh = 0, tt = 0; memset(de, 0, sizeof(de));
    de[s] = 1, q[hh] = s;
    while(hh <= tt)
    {
        int qaq = q[hh ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, q[++ tt] = to;
        }
    }
    return de[t] > 0;
}

lo dfs(int no, lo fl, int t)
{
    if(no == t)
        return fl;
    lo rt = 0, ret;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co)
        {
            ret = dfs(to, min(fl, ter[i].co), t);
            if(ret > 0)
            {
                fl -= ret, rt += ret, ter[i].co -= ret, ter[i ^ 1].co += ret;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline lo dinic(int s, int t)
{
    lo lin, rt = 0;
    while(bfs(s, t))
    {
        memcpy(he, head, sizeof(he));
        while((lin = dfs(s, 1e9 + 7, t)) > 0)
            rt += lin;
    }
    return rt;
}

inline void rebuild()
{
    for(ri i = 0; i <= tot; i += 2)
        ter[i].co = ter[i ^ 1].co = ((ter[i].co + ter[i ^ 1].co) >> 1);
}

void col(int x)
{
    flag[x] = 1;
    for(ri i = head[x]; i >= 0; i = ter[i].ne)
        if(ter[i].co && (!flag[ter[i].to]))
            col(ter[i].to);
}

void merge(int l, int r)
{
    if(l >= r)
        return;
    rebuild(); lo maxflow = dinic(a[l], a[r]);
    memset(flag, 0, sizeof(flag)), col(a[l]);
    for(ri i = 1; i <= n; i ++)
    {
        if(!flag[i])
            continue;
        for(ri j = 1; j <= n; j ++)
        {
            if(flag[j])
                continue;
            ans[i][j] = ans[j][i] = min(ans[i][j], maxflow);
        }
    }
    int ta = l - 1;
    for(ri i = l; i <= r; i ++)//按照点与s/t的连通性划分 
        if(flag[a[i]])
            tmp[++ ta] = a[i];
    int poi = ta;
    for(ri i = l; i <= r; i ++)
        if(!flag[a[i]])
            tmp[++ ta] = a[i];
    for(ri i = l; i <= r; i ++)
        a[i] = tmp[i];
    merge(l, poi), merge(poi + 1, r);
}

inline bool cmpa(node a, node b)
{
    return a.num < b.num;
}

inline bool cmpb(node a, node b)
{
    return a.pos < b.pos;
}

inline void solve()
{
    memset(head, -1, sizeof(head)), memset(ans, 63, sizeof(ans)), tot = -1;
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        a[i] = i;
    while(m --)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    merge(1, n); re(qq);
    for(ri i = 1; i <= qq; i ++)
        re(lx), Ask[i] = (node){i, lx, 0};
    sort(Ask + 1, Ask + 1 + qq, cmpa); int ta = 0;
    for(ri i = 1; i <= n; i ++)
        for(ri j = i + 1; j <= n; j ++)
            pri[++ ta] = ans[i][j];
    sort(pri + 1, pri + 1 + ta);
    int tail = 1;
    for(ri i = 1; i <= ta; i ++)
    {
        while(Ask[tail].num < pri[i] && tail <= qq)
            Ask[tail].ans = i - 1, tail ++;
    }
    while(tail <= qq)
        Ask[tail].ans = ta, tail ++;
    sort(Ask + 1, Ask + 1 + qq, cmpb);
    for(ri i = 1; i <= qq; i ++)
        cout << Ask[i].ans << '\n';
    cout << '\n';
}

int main()
{
    re(T);
    while(T --)
        solve();
}

BZOJ 4625 [BJOI2016]水晶
这个题简直是玄学……我也不知道一开始我建图错在哪里了……明明看起来没什么区别。
这个题其实也挺套路,但是我傻QAQ,你可以按照(x+y+z)mod3的结果来将点划分成三种,显然这就可以构建三分图了,然后你发现有关系的都是相邻并且mod之后可以得到012这样的……然后你就可以建个三分图跑最小割就过了。
为了方便这里可以把z这一维度给压掉。变成x-z,y-z,但是这样你算z轴的变化的时候,就必须要xy一起+/-了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 5e4 + 10;

const int bs = 3e4;

int tot = -1, t, ans, n, m, lz, lc, head[ms << 1], he[ms << 1], de[ms << 1], cnt, x[ms], y[ms], c[ms];

int l[ms], r[ms];

bool flag[ms];

struct in
{
    int to, ne, co;
}ter[ms << 5];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

map <pair<int, int>, int> vis, val;

queue <int> qwq;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), qwq.push(0), de[0] = 1;
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, qwq.push(to);
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, ret;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            ret = dfs(to, min(fl, ter[i].co));
            if(ret)
            {
                fl -= ret, rt += ret, ter[i].co -= ret, ter[i ^ 1].co += ret;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

int px[10] = {0, 0, 1, -1, 1, -1}, py[10] = {1, -1, 0, 0, 1, -1};

int main()
{
    //freopen("4625.in", "r", stdin);
    //freopen("4625.out", "w", stdout);
    re(n); memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
    {
        re(x[i]), re(y[i]), re(lz), re(c[i]), x[i] -= lz, y[i] -= lz;
        c[i] *= ((x[i] + y[i]) % 3 == 0) ? 11 : 10, ans += c[i];
        pair <int, int> tmp = make_pair(x[i], y[i]);
        if(!vis.count(tmp))
            vis[tmp] = i, val[tmp] = c[i];
        else
            flag[i] = 1, val[tmp] += c[i];
        l[i] = ++ cnt, r[i] = ++ cnt;
    }
    t = ++ cnt;
    for(ri i = 1; i <= n; i ++)
    {
        if(flag[i])
            continue;
        if((x[i] + y[i] + bs) % 3 == 1)
            build(0, r[i], val[make_pair(x[i], y[i])]);
        else if((x[i] + y[i] + bs) % 3 == 0)
            build(l[i], r[i], val[make_pair(x[i], y[i])]);
        else
            build(l[i], t, val[make_pair(x[i], y[i])]);
    }
    for(ri i = 1; i <= n; i ++)
    {
        if(flag[i])
            continue;
        for(ri j = 0; j < 6; j ++)
        {
            int tx = x[i] + px[j], ty = y[i] + py[j], pos;
            if(!vis.count(make_pair(tx, ty)))
                continue;
            pos = vis[make_pair(tx, ty)];
            if((x[i] + y[i] + bs) % 3 == 1 && (tx + ty + bs) % 3 == 0)
                build(r[i], l[pos], 1e9 + 7);
            if((x[i] + y[i] + bs) % 3 == 0 && (tx + ty + bs) % 3 == 2)
                build(r[i], l[pos], 1e9 + 7);
        }
    }
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        ans -= dfs(0, 1e9 + 7);
    }
    printf("%d.%d", ans / 10, ans % 10);
}

luogu P3227 [HNOI2013]切糕
这个题可以说是非常经典了,由它引申出来的许多题目被称为切糕模型。
每次模型转化都是转的我一脸懵逼啊……根本想不到。这个题首先你要先把点转化成边,那么对于每一个纵轴,这样划分成R+1层,这些点分别是,0-1的边,1-2的边………………那么边权显然就是val[i][j][k]。
之后你要考虑|f(i,j)-f(x,y)| \leq D,换句话说只要让这个条件不成立的时候还存在一条流就行,因此向周围的单位降低D+1个高度建一条无限边。

// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 3e5 + 10;

int P, Q, R, D, s, t, tot = -1, head[ms], he[ms], de[ms], val[45][45][45];

queue <int> q;

int px[6] = {-1, 1, 0, 0}, py[6] = {0, 0, -1, 1};

struct in
{
    int to, ne, co;
}ter[ms << 1];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de)), q.push(0), de[0] = 1;
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, q.push(to);
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, ret;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            ret = dfs(to, min(fl, ter[i].co));
            if(ret)
            {
                fl -= ret, rt += ret, ter[i].co -= ret, ter[i ^ 1].co += ret;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int dinic()
{
    int rt = 0;
    while(bfs())
        memcpy(he, head, sizeof(he)), rt += dfs(0, 1e9 + 7);
    return rt;
}

int main()
{
    re(P), re(Q), re(R), re(D), t = P * Q * (R + 1) + 5;
    memset(head, -1, sizeof(head));
    for(ri k = 1; k <= R; k ++)
        for(ri i = 1; i <= P; i ++)
            for(ri j = 1; j <= Q; j ++)
                re(val[i][j][k]);
    for(ri i = 1; i <= P; i ++)
        for(ri j = 1; j <= Q; j ++)
        {
            int pos = (i - 1) * Q + j + 1;
            build(0, pos, 1e9 + 7), build(P * Q * R + pos, t, 1e9 + 7);
            for(ri k = 1; k <= R; k ++)
                build(P * Q * (k - 1) + pos, P * Q * k + pos, val[i][j][k]);
        }
    for(ri i = 1; i <= P; i ++)
        for(ri j = 1; j <= Q; j ++)
            for(ri l = 0; l < 4; l ++)
            {
                int tx = i + px[l], ty = j + py[l];
                if(tx < 1 || tx > P || ty < 1 || ty > Q)
                    continue;
                for(ri k = D + 1; k <= R + 1; k ++)
                    build(P * Q * (k - 1) + (i - 1) * Q + j + 1,
                        P * Q * (k - D - 1) + (tx - 1) * Q + ty + 1, 1e9 + 7);
            }
    printf("%d\n", dinic());
    system("pause");
}

luogu P3749 [SHOI2017]寿司餐厅
这个题目又双叒验证了我是个sb……
首先很直接的,会想到d_{i,j}只需要和d_{i,j-1},d_{i+1,j}连边,但是具体怎么连我完全没想到啊…………………………
建图是这样的,因为是最大权闭合子图,所以要求所有的正权点和源点相连,边权则是正的点权,所有的负权点和汇点相连,这首先是没有任何问题的,然后所有的寿司向汇点连边,边权为ma_i^2,然后d_{i,j}只需要和d_{i,j-1},d_{i+1,j}各连条无限边,防止隔断,d_{i,i}要和他所对应的寿司编号连无限边,向汇点连接一条边权为a_i的边,这样就能使得你选择这个点的时候同时产生相应的费用了

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int tot = -1, ans, t, he[30030], head[30030], n, m, a[110], d[110][110], de[30030];

int cnt, posa[1010], posd[110][110];

struct in
{
    int to, ne, co;
}ter[300030];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

queue <int> q;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[0] = 1, q.push(0);
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                q.push(to), de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, c;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(fl, ter[i].co));
            if(c)
            {
                fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int dinic()
{
    int rt = 0, tmp;
    while(bfs())
    {
        memcpy(he, head, sizeof(he)); 
        while((tmp = dfs(0, 1e9 + 7)) > 0)
            rt += tmp;
    }
    return rt;
}

inline void init()
{
    re(n), re(m), t = ++ cnt; memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
    {
        re(a[i]);
        if(!posa[a[i]])
            posa[a[i]] = ++ cnt, build(cnt, t, m * a[i] * a[i]);
    }
    for(ri i = 1; i <= n; i ++)
        for(ri j = i; j <= n; j ++)
        {
            re(d[i][j]), posd[i][j] = ++ cnt;
            if(d[i][j] > 0)
                build(0, cnt, d[i][j]), ans += d[i][j];
            else
                build(cnt, t, - d[i][j]);
        }
    for(ri i = 1; i <= n; i ++)
        build(posd[i][i], posa[a[i]], 1e9 + 7), build(posd[i][i], t, a[i]);
    for(ri i = 1; i <= n; i ++)
        for(ri j = i + 1; j <= n; j ++)
            build(posd[i][j], posd[i][j - 1], 1e9 + 7), build(posd[i][j], posd[i + 1][j], 1e9 + 7);
}

int main()
{
    init(), printf("%d", ans - dinic());
}

luogu SP839 OPTM – Optimal Marks
这个题目又是一个经典的2选1问题啊……首先二进制,每一位都是独立的,意味着我可以按位考虑。那么显然我要拆分二进制,那么现在这个问题就变成了每一位上是0/1,如果两个数在这一位上不一样并且之间有边,就会产生1的代价。那么现在我们可以这么建图,先考虑所有点都没选择的情况,这个时候显然你都选0就好了……也就说是那些被钦定的点给我们产生了影响,因此你把和源点相连代表选1,和汇点相连代表选0,开始对于那些钦定的点按照这一位上是0还是1连接源点/汇点(流量都是无穷)。然后还是按照原图的关系建边,流量为1,这样在图上跑最小割,这个割就是不得不选的那些代价。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int T, n, m, K, head[550], he[550], t, ff[3030], tt[3030], tot, Mark[550], ans[550], pos[550];

int de[550];

bool flag[550];

struct in
{
    int to, ne, co;
}ter[100010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
}

queue <int> q;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[0] = 1, q.push(0);
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                q.push(to), de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, c;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(fl, ter[i].co));
            if(c)
            {
                fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline void dinic()
{
    int tmp;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while((tmp = dfs(0, 1e9 + 7)) > 0);
    }
}

inline void init()
{
    tot = -1, memset(head, -1, sizeof(head)), memset(flag, 0, sizeof(flag));
}

void change(int no, int x)
{
    flag[no] = 1, ans[no] |= x;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
        if(ter[i].co && (!flag[ter[i].to]))
            change(ter[i].to, x);
} 

inline void solve()
{
    re(n), re(m);
    for(ri i = 1; i <= m; i ++)
        re(ff[i]), re(tt[i]);
    memset(ans, 0, sizeof(ans)); re(K);
    for(ri i = 1; i <= K; i ++)
        re(pos[i]), re(Mark[i]);
    t = n + 1;
    for(ri i = 30; i >= 0; i --)
    {
        init();
        for(ri j = 1; j <= m; j ++)
            build(ff[j], tt[j], 1), build(tt[j], ff[j], 1);
        for(ri j = 1; j <= K; j ++)//强制选1是连源点,选0连接汇点 
        {
            if(Mark[j] & (1 << i)) 
                build(0, pos[j], 1e9 + 7), build(pos[j], 0, 0);
            else
                build(pos[j], t, 1e9 + 7), build(t, pos[j], 0);
        }
        dinic(), change(0, 1 << i);
    }
    for(ri i = 1; i <= n; i ++)
        printf("%d\n", ans[i]);
}

int main()
{
    re(T);
    while(T --)
        solve();
}

luogu P4003 无限之环
这个题好tm牛逼……我不会自闭了。
这个题目首先看到闭合我头都炸了……妈耶这是啥情况,我不会用网络流构造闭合的回路啊,但是考虑这个题目,一个水管口只可能会和周围的另一个水管口配对……这也就意味着我们可以往二分图去考虑,首先对整个地图黑白染色,对每一个格子拆成上下左右四个点,之后按照水管口的方向建边不带费用流量都1。这样我们就做完不带修改的情况了。
那么待修改的呢?待修改意味着我们可以改变原有的水管方向去连向其他方向的点,也就说内部连边。看下代码+画图应该是能理解的……考虑5种图就好。每次费用就是我们需要修改到那个状态所花费的旋转次数。
有史以来写过最长的费用流。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, m, tot = -1, sum, head[10010], dis[10010], fl[10010], pre[10010], t, cnt, ans, Cost;

queue <int> qwq;

bool flag[10010];

struct in
{
    int to, ne, fl, co;
}ter[200020];

inline void build(int f, int l, int fl, int co)
{
    ter[++ tot] = (in){l, head[f], fl, co}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0, -co}, head[l] = tot;
}

int lx, id[2020][2020][4];

int px[4] = {-1, 0, 1, 0}, py[4] = {0, 1, 0, -1};

inline int lowbit(int x)
{
    return x & (-x);
}

inline int askbit(int x)
{
    int rt = 0;
    while(x)
        rt ++, x -= lowbit(x);
    return rt;
}

inline void link(int x, int y, int fl, int co, int col)
{
    if(col == 1)
        build(x, y, fl, co);
    else if(x == 0)
        build(y, t, fl, co);
    else
        build(y, x, fl, co);
}

inline void work(int x, int y, int ty, int dir, int col)
{
    int *A = id[x][y];
    if(ty == 1)//射线的时候 
    {
        link(0, A[dir], 1, 0, col), link(A[dir], A[(dir + 1) % 4], 1, 1, col);
        link(A[dir], A[(dir + 2) % 4], 1, 2, col), link(A[dir], A[(dir + 3) % 4], 1, 1, col);
    }
    else if(ty == 2)//两个接口挨着 
    {
        link(0, A[dir], 1, 0, col), link(0, A[(dir + 1) % 4], 1, 0, col);
        link(A[dir], A[(dir + 2) % 4], 1, 1, col), link(A[(dir + 1) % 4], A[(dir + 3) % 4], 1, 1, col);
    }
    else if(ty == 3)//直线型的,不能转 
        link(0, A[dir], 1, 0, col), link(0, A[(dir + 2) % 4], 1, 0, col);
    else if(ty == 4)//那种3个接口的 
    {
        link(0, A[dir], 1, 0, col), link(0, A[(dir + 1) % 4], 1, 0, col), link(0, A[(dir + 2) % 4], 1, 0, col);
        link(A[dir], A[(dir + 3) % 4], 1, 1, col), link(A[(dir + 1) % 4], A[(dir + 3) % 4], 1, 2, col), link(A[(dir + 2) % 4], A[(dir + 3) % 4], 1, 1, col);
    }
    else//四个方向都有…… 
    {
        link(0, A[dir], 1, 0, col), link(0, A[(dir + 1) % 4], 1, 0, col);
        link(0, A[(dir + 2) % 4], 1, 0, col), link(0, A[(dir + 3) % 4], 1, 0, col);
    }
}

inline bool spfa()
{
    memset(flag, 0, sizeof(flag)), memset(fl, 0, sizeof(fl)), memset(dis, 63, sizeof(dis));
    dis[0] = 0, fl[0] = 1e9 + 7, qwq.push(0), flag[0] = 1;
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].fl && dis[to] > dis[qaq] + ter[i].co)
            {
                dis[to] = dis[qaq] + ter[i].co, fl[to] = min(fl[qaq], ter[i].fl), pre[to] = i;
                if(!flag[to])
                    qwq.push(to), flag[to] = 1;
            }
        }
        flag[qaq] = 0;
    }
    return fl[t] > 0;
}

inline void change()
{
    ans += fl[t], Cost += fl[t] * dis[t];
    for(ri i = t; i; i = ter[pre[i] ^ 1].to)
        ter[pre[i]].fl -= fl[t], ter[pre[i] ^ 1].fl += fl[t];
}

int main()
{
    re(n), re(m); memset(head, -1, sizeof(head)), t = ++ cnt;
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            re(lx);
            for(ri k = 0; k < 4; k ++)
                id[i][j][k] = ++ cnt;
            if(lx == 1)
                work(i, j, 1, 0, (i + j) & 1);
            else if(lx == 2)
                work(i, j, 1, 1, (i + j) & 1);
            else if(lx == 3)
                work(i, j, 2, 0, (i + j) & 1);
            else if(lx == 4)
                work(i, j, 1, 2, (i + j) & 1);
            else if(lx == 5)
                work(i, j, 3, 0, (i + j) & 1);
            else if(lx == 6)
                work(i, j, 2, 1, (i + j) & 1);
            else if(lx == 7)
                work(i, j, 4, 0, (i + j) & 1);
            else if(lx == 8)
                work(i, j, 1, 3, (i + j) & 1);
            else if(lx == 9)
                work(i, j, 2, 3, (i + j) & 1);
            else if(lx == 10)
                work(i, j, 3, 1, (i + j) & 1);
            else if(lx == 11)
                work(i, j, 4, 3, (i + j) & 1);
            else if(lx == 12)
                work(i, j, 2, 2, (i + j) & 1);
            else if(lx == 13)
                work(i, j, 4, 2, (i + j) & 1);
            else if(lx == 14)
                work(i, j, 4, 1, (i + j) & 1);
            else if(lx == 15)
                work(i, j, 5, 0, (i + j) & 1);
            sum += askbit(lx);
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            if((i + j) & 1)
                for(ri k = 0; k < 4; k ++)
                {
                    int tx = i + px[k], ty = j + py[k];
                    if(tx < 1 || tx > n || ty < 1 || ty > m)
                        continue;
                    build(id[i][j][k], id[tx][ty][(k + 2) % 4], 1, 0);
                }
    while(spfa())
        change();
    printf("%d", (ans == (sum >> 1)) ? Cost : -1);
}

ZOJ 2314 Reactor Cooling
这算是一个上下界网络流的裸题,怎么证明我也不会……
先记下最低流量,同时记录每个点的流入-流出,然后每条边按照最大流量-最小流量建边。
同时设置一个源点一个汇点,设第i个点的流入-流出为a_i,那么如果a_i > 0,就建一条从源点到i的边,流量为a_i,否则就建一个流量为-a_i的,从i流到t的边。记录所有a_i大于0的和。
对这个图跑一边最大流,然后每条边的答案就是最低流量+反向边流量

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e5 + 10;

int T, n, m, t, la, lb, lc, ld, tot = -1, ans, Flow, head[ms], he[ms], de[ms], a[ms], in[ms], inv[ms];

struct edge
{
    int to, ne, co;
}ter[ms];

inline void build(int f, int l, int c)
{
    //cout << f << ' ' << l << ' ' << c << '\n';
    ter[++ tot] = (edge){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (edge){f, head[l], 0}, head[l] = tot;
}

queue <int> qwq;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[0] = 1, qwq.push(0);
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, qwq.push(to);
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, c;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(fl, ter[i].co));
            if(c)
            {
                fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int dinic()
{
    int rt = 0, tmp;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while((tmp = dfs(0, 1e9 + 7)) > 0)
            rt += tmp;
    }
    return rt;
}

int main()
{
    re(T);
    while(T --)
    {
        re(n), re(m), tot = -1, t = n + 1, Flow = 0; 
        memset(a, 0, sizeof(a)), memset(head, -1, sizeof(head));
        for(ri i = 1; i <= m; i ++)
        {
            re(la), re(lb), re(lc), re(ld);
            in[i] = lc, a[lb] += lc, a[la] -= lc;
            build(la, lb, ld - lc), inv[i] = tot;
        }
        for(ri i = 1; i <= n; i ++)
        {
            if(a[i] > 0)
                build(0, i, a[i]), Flow += a[i];
            else if(a[i] < 0)
                build(i, t, -a[i]);
        }
        ans = dinic(); 
        if(ans == Flow)
        {
            printf("YES\n");
            for(ri i = 1; i <= m; i ++)
                printf("%d\n", in[i] + ter[inv[i]].co);
        }
        else
            printf("NO\n");
    }
}

luogu P4311 士兵占领
听说这个题目可以上下界费用流什么的……反正打死我也不会。
说个简单点的办法,对于每行建个点,从源点流向他,边权是它最多不要的人数,对于每列也是类似,只不过你往汇点建边就是了。
把每个格子加在中间,然后向行和列建一条流量为1的边就是了。
无解就是某行某列都放上棋子也不满足条件。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

bool flag[110][110];

int n, m, t, k, cnt, lx, ly, ans, e[12000], a[110], b[110], he[12000], tot = -1, head[12000];

int rh[110], rl[110];

int de[12000];

struct in
{
    int to, ne, co;
}ter[100010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

queue <int> qwq;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[0] = 1, qwq.push(0);
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, qwq.push(to);
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t || (!fl))
        return fl;
    int rt = 0, c;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(fl, ter[i].co));
            if(c)
            {
                fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int dinic()
{
    int rt = 0, tmp;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while((tmp = dfs(0, 1e9 + 7)) > 0)
            rt += tmp;
    }
    return rt;
}

int main()
{
    re(n), re(m), re(k), t = n + m + n * m + 1, cnt = n + m, ans = n * m - k;
    memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
        re(a[i]), rh[i] = m - a[i];
    for(ri i = 1; i <= m; i ++)
        re(b[i]), rl[i] = n - b[i];
    for(ri i = 1; i <= k; i ++)
        re(lx), re(ly), flag[lx][ly] = 1, rh[lx] --, rl[ly] --;
    for(ri i = 1; i <= n; i ++)
    {
        if(rh[i] < 0)
        {
            printf("JIONG!"); return 0;
        }
        build(0, i, rh[i]);
    }
    for(ri i = 1; i <= m; i ++)
    {
        if(rl[i] < 0)
        {
            printf("JIONG!"); return 0;
        }
        build(i + n, t, rl[i]);
    }
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            if(!flag[i][j])
                cnt ++, build(i, cnt, 1), build(cnt, j + n, 1);
    ans -= dinic(); printf("%d", ans);
}

1 thought

发表评论

电子邮件地址不会被公开。 必填项已用*标注