网络流专题

目录
  1. 1. 实现
    1. 1.1. ISAP
    2. 1.2. Dinic
    3. 1.3. MCMF
    4. 1.4. read
  2. 2. 网络流 24 题
    1. 2.1. 01
    2. 2.2. 02
    3. 2.3. 03
    4. 2.4. 04
    5. 2.5. 05
    6. 2.6. 06
    7. 2.7. 07
    8. 2.8. 08
    9. 2.9. 09
    10. 2.10. 10
    11. 2.11. 11
    12. 2.12. 12
    13. 2.13. 汇总

实现

由于网络流问题难点在于建模，实现网络流的代码几乎可以不变，为此，特将下文中将会多次使用到的代码给罗列出来。

ISAP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
namespace ISAP {/*{{{*/
    static const int MAXN = 10000+10;
    static const int INF = 0x3f3f3f3f;

    struct edge {
        int from, to, cap, flow;
        edge(int from=0, int to=0, int cap=0, int flow=0):
            from(from), to(to), cap(cap), flow(flow) {}
    };
 
    int s, t, n;
    int cnt[MAXN];
    int cur[MAXN];
    int path[MAXN];
    int dist[MAXN];
    std:: vector<edge> edges;
    std:: vector<int> G[MAXN];
    std:: queue<int> Q;
 
    void addedge(int from, int to, int cap) {
        int siz = edges.size();
        edges.push_back(edge(from, to, cap, 0));
        edges.push_back(edge(to, from, 0, 0));
        G[from].push_back(siz);
        G[to].push_back(siz+1);
    }
    
    void BFS() {
        memset(dist, 0x3f, sizeof dist);
        Q.push(t);
        dist[t] = 0;
 
        while( !Q.empty() ) {
            int o = Q.front(); Q.pop();
            for(int i=0; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( dist[e.to] == INF && e.cap == 0 ) {
                    dist[e.to] = dist[o] + 1;
                    Q.push(e.to);
                }
            }
        }
    }

    int augment() {
        int mif = INF; 
        for(int o=t; o != s;) {
            edge& e = edges[path[o]];
            mif = std:: min(mif, e.cap-e.flow);
            o = e.from;
        }
        for(int o=t; o != s;) {
            edges[path[o]].flow += mif;
            edges[path[o]^1].flow -= mif;
            o = edges[path[o]].from;
        }
        return mif;
    }

    int maxflow() {
        BFS();
        memset(cur, 0, sizeof cur);
        memset(cnt, 0, sizeof cnt);
        for(int i=0; i < n; ++i) 
            if( dist[i] < n ) ++cnt[dist[i]];

        int ans = 0;
        for(int o=s; dist[o] < n; ) {
            if( o == t ) ans += augment(), o = s;
            bool ok = false;
            for(int i=cur[o]; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( e.cap > e.flow && dist[o] == dist[e.to]+1 ) {
                    ok = true;
                    cur[o] = i;
                    path[e.to] = G[o][i];
                    o = e.to;
                    break;
                }
            }
            if( !ok ) {
                int d = n-1;
                for(int i=0; i < G[o].size(); ++i) {
                    edge& e = edges[G[o][i]];
                    if( e.cap > e.flow ) d = std:: min(d, dist[e.to]);
                }
                if( --cnt[dist[o]] == 0 ) break;
                ++cnt[dist[o] = d+1];
                cur[o] = 0;
                if( o != s ) o = edges[path[o]].from;
            }
        }
        return ans;
    }

    void solve();
    void solve(int);
    void solve(int, int);
    void solve(int, int, int);
};/*}}}*/

Dinic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
namespace Dinic {/*{{{*/
    struct edge {
        int from, to, cap, flow;
        edge(int from=0, int to=0, int cap=0, int flow=0):
            from(from), to(to), cap(cap), flow(flow) {}
    };

    int s, t;
    int cur[MAXN];
    int dist[MAXN];
    std:: queue<int> Q;
    std:: vector<edge> edges;
    std:: vector<int> G[MAXN];

    void addedge(int from, int to, int cap) {
        int siz = edges.size();
        edges.push_back(edge(from, to, cap, 0));
        edges.push_back(edge(to, from, 0, 0));
        G[from].push_back(siz);
        G[to].push_back(siz+1);
    }

    bool BFS() {
        memset(dist, -1, sizeof dist);

        Q.push(s);
        dist[s] = 0;

        while( !Q.empty() ) {
            int o = Q.front(); Q.pop();
            for(int i=0; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( dist[e.to] != -1 || e.cap <= e.flow ) continue;
                dist[e.to] = dist[o]+1;
                Q.push(e.to);
            }
        }

        return dist[t] != -1;
    }

    int DFS(int o, int minflow) {
        if( o == t || minflow == 0 ) return minflow;
        int flow = 0;
        for(int& i=cur[o]; i < G[o].size(); ++i) {
            edge& e = edges[G[o][i]];
            if( dist[e.to] == dist[o]+1 ) {
                int f = DFS(e.to, std:: min(minflow, e.cap-e.flow));
                if( f <= 0 ) continue;
                e.flow += f;
                edges[G[o][i]^1].flow -= f;
                flow += f;
                minflow -= f;
                if( minflow == 0 ) break;
            }
        }
        return flow;
    }

    int maxflow() {
        int ans = 0;
        while( BFS() ) {
            memset(cur, 0, sizeof cur);
            ans += DFS(s, INF);
        }
        return ans;
    }

    void solve();
    void solve(int);
    void solve(int, int);
    void solve(int, int, int);
};/*}}}*/

MCMF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
namespace MCMF {/*{{{*/
    const int MAXN = 10000+10;
    const int INF = 0x3f3f3f3f;

    struct edge {
        int from, to, cap, flow, cost;
        edge(int from=0, int to=0, int cap=0, int flow=0, int cost=0):
            from(from), to(to), cap(cap), flow(flow), cost(cost) {}
    }; 

    int s, t;
    int cost, flow;
    int path[MAXN];
    int dist[MAXN];
    std:: vector<edge> edges;
    std:: vector<int> G[MAXN];

    void init(int source=0, int converge=1, int N=MAXN) {
        s = source; 
        t = converge;
        cost = 0;
        flow = 0;
        edges.clear();
        for(int i=0; i < N; ++i) G[i].clear();
    }

    void addedge(int from, int to, int cap, int cost) {
        int siz = edges.size();
        edges.push_back(edge(from, to, cap, 0, cost));
        edges.push_back(edge(to, from, 0, 0, -cost));
        G[from].push_back(siz);
        G[to].push_back(siz+1);
    }

    bool SPFA() {
        static std:: queue<int> Q;
        static bool inq[MAXN];

        memset(dist, 0x3f, sizeof dist);
        Q.push(s);
        inq[s] = true;
        dist[s] = 0;
 
        while( !Q.empty() ) {
            int o = Q.front(); Q.pop();
            for(int i=0; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( e.cap > e.flow && dist[e.to] > dist[o]+e.cost ) {
                    dist[e.to] = dist[o] + e.cost;
                    path[e.to] = G[o][i];
                    if( inq[e.to] ) continue;
                    inq[e.to] = true;
                    Q.push(e.to);
                }
            }
            inq[o] = false;
        }
 
        return dist[t] != INF;
    }

    std:: pair<int, int> mincostmaxflow() {
        while( SPFA() ) {
            int mif = INF;
            for(int o=t; o != s;) {
                edge& e = edges[path[o]];
                mif = std:: min(mif, e.cap-e.flow);
                o = e.from;
            }
            for(int o = t; o != s;) {
                edges[path[o]].flow += mif;
                edges[path[o]^1].flow -= mif;
                o = edges[path[o]].from;
            }
            flow += mif;
            cost += mif*dist[t];
        }
        return std:: make_pair(flow, cost);
    }

    void solve();
    void solve(int);
    void solve(int, int);
    void solve(int, int, int);
};/*}}}*/

read

1
2
3
4
5
6
7
8
9
10
inline int read() {/*{{{*/
    bool positive = true;
    char c = getchar();
    int s = 0;
    for(; c < '0' || c > '9'; c=getchar())
        if( c == '-' ) positive = false;
    for(; c >= '0' && c <= '9'; c=getchar())
        s = s*10 + c-'0';
    return positive? s: -s;
}/*}}}*/

网络流 24 题

01

**Power OJ/1736 *[飞行员配对方案问题](https://www.oj.swust.edu.cn/problem/show/1736)*** 经典的二分图模型。 - 外籍飞行员作为左侧点，英国飞行员作为右侧点，可以互相配合的飞行员之间连一条容量为 1 的边 - 建立源点 $s$，并从 $s$ 对左侧的每个点引一条容量为 1 的边 - 建立汇点 $t$，并从右侧的每个点向 $t$ 引一条容量为 1 的边

跑最大流。
至于方案，仅需考虑满流的边 $\left< \mu,\nu \right>$（其中 $\mu \in$ 左侧的点集，$\nu \in$ 右侧的点集），那么 $\mu$ 和 $\nu$ 是一对搭档。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void ISAP:: solve(int N, int M) {/*{{{*/
    s = 0; t = M+1; n = M+2;
    int ans = maxflow();
    if( ans > 0 ) {
        printf("%d\n", ans);
        for(int o=0; o < N; ++o) {
            edge& e = edges[G[0][o]];
            if( e.cap == e.flow ) {
                for(auto& i: G[e.to]) {
                    edge& e2 = edges[i];
                    if( e2.cap == e2.flow ) {
                        printf("%d %d\n", e.to, e2.to);
                        break;
                    }
                }
            }
        }
    } else puts("No Solution!");
}

int main()
{
    int N = read();
    int M = read();

    for(int i=1; i <= N; ++i) 
        ISAP:: addedge(0, i, 1);

    for(int i=N+1; i <= M; ++i)
        ISAP:: addedge(i, M+1, 1);

    while( true ) {
        int u = read();
        int v = read();
        if( u == -1 && v == -1 ) break;
        if( u > v ) std:: swap(u, v);
        ISAP:: addedge(u, v, 1);
    }

    ISAP:: solve(N, M);
    return 0;
}/*}}}*/

02

**Power OJ/1737 *[太空飞行计划问题](https://www.oj.swust.edu.cn/problem/show/1737)*** 经典的最大权闭合图问题。 关于最大权闭合图可以参见 ***[网络流基础之最大权闭合图](http://littleclown.github.io/2016/07/24/Study-GT-network-flow-Maximum-weight-Closure-of-a-Graph/)***。 - 设实验 $i$ 获利为 $x\_i$，实验仪器 $j$ 花费为 $y\_j$ - 将每个实验与实验所需仪器连边，且容量设为 $\infty$ - 建立源点 $s$，并从 $s$ 对所有的实验引一条容量为 $\alpha\times x+\beta$ 的边（其中，$\alpha$ 与 $\beta$ 的作用及取值在 ***[网络流基础之最大权闭合图](http://littleclown.github.io/2016/07/24/Study-GT-network-flow-Maximum-weight-Closure-of-a-Graph/)*** 一文中有详细讨论） - 建立汇点 $t$，并从所有的实验仪器向 $t$ 引一条容量为 $\alpha\times y$ 的边

跑最大流，$\big(\sum x \big)$-最大流量 即是答案。
至于方案，仅需考虑满流的边所连接的节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
void ISAP:: solve(int M, int N, int tot) {/*{{{*/
        static bool used[MAXN];
        static std:: stack<int> st;
        memset(used, 0, sizeof used);

        s = 0; t = M+N+1; n = M+N+2;
        int ans = tot-maxflow();
        
        st.push(s);
        while( !st.empty() ) {
            int o = st.top(); st.pop();
            used[o] = true;
            for(auto& i: G[o]) {
                edge& e = edges[i];
                if( e.cap > e.flow && !used[e.to] ) 
                    st.push(e.to);
            }
        }

        for(int i=1; i <= M; ++i) if( used[i] ) printf("%d ", i); putchar('\n');
        for(int i=1; i <= N; ++i) if( used[M+i] ) printf("%d ", i); putchar('\n');
        printf("%d\n", ans>>16);
   
}

const int INF = 0x3f3f3f3f;
const int partail = (1<<16)-1;

char s[10000], *ss;
inline int nextint(char* &s) {
    for(; *s < '0' || *s > '9'; s++)
        if( *s == '\n' ) return -1;
    int num = 0;
    for(; *s >= '0' && *s <= '9'; s++)
        num = num*10 + *s-'0';
    return num;
}

int main()
{
    int M = read();
    int N = read();
    int tot = 0;

    for(int i=1; i <= M; ++i) {
        for(ss=s; (*ss=getchar()) == '\n'; );
        for(ss=s+1; (*ss=getchar()) != '\n'; ++ss);
        ss = s;
        int val = nextint(ss)<<16|1;
        ISAP:: addedge(0, i, val);
        for(int id; (id=nextint(ss)) != -1;)
            ISAP:: addedge(i, M+id, INF);
        tot += val;
    }
    for(int i=1; i <= N; ++i) {
        int val = read()<<16;
        ISAP:: addedge(M+i, M+N+1, val);
    }

    ISAP:: solve(M, N, tot);
    return 0;
}/*}}}*/

03

**Power OJ/1738 *[最小路径覆盖问题](https://www.oj.swust.edu.cn/problem/show/1738)*** 经典的有向无环图最小路径覆盖问题。 - 最小路径覆盖要求的是有向无环图，将原图每个点拆成两个，显然新图是一个二分图 - 求出二分图最大匹配，最小路径覆盖数=原图点数-新图最大匹配数。

简单证明：初始时可以看做有 $N$ 个长度为 0 的路径，每得到一个匹配相当于合并两条路径。
至于方案，从左侧任意一个未访问过的点出发，经沿着交替路走，得到的就是最小路径覆盖中的一条路径。
考虑到使用网络流求出路径比较麻烦 = =，仅给出二分图的 增广路算法 的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>/*{{{*/

const int MAXN = 1000+10;
const int INF = 0x3f3f3f3f;

namespace hungary {
    int L, R;
    std:: vector<int> G[MAXN];
    int left[MAXN], right[MAXN];
    bool mark[MAXN];

    void init(int L=0, int R=0) {
        hungary:: L = L;
        hungary:: R = R;
        for(int u=1; u <= L; ++u ) G[u].clear();
    }

    bool match(int u) {
        for(int i=0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if( !mark[v] ) {
                mark[v] = true;
                if( !left[v] || match(left[v]) ) {
                    left[v] = u;
                    right[u] = v;
                    return true;
                }
            }
        }
        return false;
    }

    void solve() {
        memset(left, 0, sizeof left);
        memset(right, 0, sizeof right);

        int ans = 0;
        for(int u=1; u <= L; ++u) if( !right[u] ) {
            memset(mark, 0, sizeof mark);
            if( match(u) ) ++ans;
        }

        memset(mark, 0, sizeof mark);
        mark[0] = true;
        for(int o=1; o <= L; ++o) if( !mark[o] ) {
            mark[o] = true;
            printf("%d", o);
            for(int u=right[o]; !mark[u]; u=right[u]) {
                mark[u] = true; 
                printf(" %d", u);
            } 
            putchar('\n');
        }
        printf("%d\n", L-ans);
    }
};

inline int read() {
    bool positive = true;
    char c = getchar();
    int s = 0;
    for(; c < '0' || c > '9'; c=getchar())
        if( c == '-' ) positive = false;
    for(; c >= '0' && c <= '9'; c=getchar())
        s = s*10 + c-'0';
    return positive? s: -s;
}

int main()
{
    int N = read();
    int M = read();

    hungary:: init(N, N);
    for(int i=1; i <= M; ++i) {
        int u = read();
        int v = read();
        hungary:: G[u].push_back(v);
    }

    hungary:: solve();
    return 0;
}/*}}}*/

04

**Power OJ/1739 *[魔术球问题](https://www.oj.swust.edu.cn/problem/show/1739)*** 经典的有向无环图最小路径覆盖问题。 - 同样地，拆点得到二分图结构 - 如果 $\mu$ 是左侧的点，$\nu$ 是右侧的点，且 $\mu+\nu$ 是一个完全平方数，那么连一条从 $\mu$ 到 $\nu$ 的边 - 逐渐加点，直到最小覆盖数超过给定值终止 - 假如在 $N+1$ 的时候终止，可以考虑对于前面 $N$ 个点中会与 $N+1$ 形成完全平方数的点删掉最后一条边，再跑一遍最大匹配。

路径的问题和 03 一样，不再赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>/*{{{*/

const int MAXN = 10000+10;
const int INF = 0x3f3f3f3f;

namespace hungary {
    int L, R;
    bool mark[MAXN];
    int left[MAXN], right[MAXN];
    std:: vector<int> G[MAXN];

    void init(int L=0, int R=0) {
        hungary:: L = L;
        hungary:: R = R;
        for(int u=1; u <= L; ++u ) G[u].clear();
    }

    bool match(int u) {
        for(int i=0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if( !mark[v] ) {
                mark[v] = true;
                if( !left[v] || match(left[v]) ) {
                    left[v] = u;
                    right[u] = v;
                    return true;
                }
            }
        }
        return false;
    }

    int maxmatch() {
        int ans = 0;
        for(int u=1; u <= L; ++u) if( !right[u] ) {
            memset(mark, 0, sizeof mark);
            if( match(u) ) ++ans;
        }
        return ans;
    }

    void solve(int N) {
        static std:: vector<int> A;
        for(int i=1; i <= 100; ++i) A.push_back(i*i);
        memset(left, 0, sizeof left);
        memset(right, 0, sizeof right);

        init(N, N);
        for(int i=1; i <= N; ++i)
            for(auto& a: A) if( a-i >= 1 && a-i < i ) G[a-i].push_back(i);
        int ans = maxmatch();

        while( true ) {
            ++L, ++R;
            for(auto& a: A) if( a-L >= 1 && a-L < L ) G[a-L].push_back(L);
            ans += maxmatch();
            if( L-ans > N ) break;
        }

        for(auto& a: A) if( a-L >= 1 && a-L < L ) G[a-L].pop_back();
        right[left[L]] = 0;
        --L; --R;
        maxmatch();

        printf("%d\n", L);
        memset(mark, 0, sizeof mark);
        mark[0] = true;
        for(int o=1; o <= L; ++o) if( !mark[o] ) {
            mark[o] = true;
            printf("%d", o);
            for(int u=right[o]; !mark[u]; u=right[u]) {
                mark[u] = true; 
                printf(" %d", u);
            } 
            putchar('\n');

        }
    }
};

int main()
{
    int N; std:: cin >> N;
    hungary:: solve(N);
    return 0;
}/*}}}*/

05

**Power OJ/1740 *[圆桌问题](https://www.oj.swust.edu.cn/problem/show/1740)*** 经典的二分图多重匹配问题。 - 将不同单位作为左侧点，不同圆桌作为右侧点，每个左侧点与每个右侧点连接一条容量为 1 的边 - 建立源点 $s$，并从 $s$ 向所有的左侧点引一条容量为 $cap\_i$ （第 $i$ 个单位的人数）的边 - 建立汇点 $t$，并从所有的右侧点向 $t$ 引一条容量为 $cap\_j$ （第 $j$ 张圆桌的容量）的边 跑最大流。 - 若满流，则有解，方案仅需考虑每个左侧点引出的满流边即可 - 若不能满流，则无解 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void ISAP:: solve(int M, int N, int tot) {/*{{{*/
    s = 0; t = M+N+1; n = M+N+2;
    int ans = maxflow();
    if( ans < tot ) { puts("0"); return; }

    puts("1");
    for(int o=1; o <= M; ++o) {
        for(auto& i: G[o]) {
            edge& e = edges[i];
            if( e.cap > 0 && e.cap == e.flow ) printf("%d ", e.to-M);
        }
        printf("\n");
    }
}
 
int main()
{
    int M = read();
    int N = read();
    int tot = 0;
 
    for(int i=1; i <= M; ++i) {
        int val = read();
        tot += val;
        ISAP:: addedge(0, i, val);
        for(int j=1; j <= N; ++j)
            ISAP:: addedge(i, M+j, 1);
    }
 
    for(int i=1; i <= N; ++i) {
        int val = read();
        ISAP:: addedge(M+i, N+M+1, val);
    }
 
    ISAP:: solve(M, N, tot);
    return 0;
}/*}}}*/

06

**Power OJ/1741 *[最长递增子序列问题](https://www.oj.swust.edu.cn/problem/show/1741)*** 经典的最多最长不相交路径问题。 不妨记第 $i$ 个数大小为 $A\_i$。 为了保证每个点只使用一次，拆点。不妨假设原序列第 $i$ 个数对应点 $x\_i$，将其拆成 $x\_i$ 和 $x'\_i$。 1. 定义 $dp[i]$ 为以第 $i$ 个数为结尾的最长上升子序列的长度，$O(N^2)$ 的动态规划 2. 记最长上升子序列长度为 $ans=\max\big\lbrace dp[i] \big| 1\leqslant i\leqslant N\big\rbrace$。 - 对于任意 $1\leqslant i\leqslant N$，从 $x\_i$ 向 $x'\_i$ 引一条容量为 1 的边（以保证第 $i$ 个数只使用一次） - 若 $A\_i < A\_j$ 且 $dp[i]+1=dp[j]$，则从 $x\_i'$ 向 $x\_j$ 引一条容量为 1 的边 - 建立源点 $s$，从 $s$ 向 $\big\lbrace x\_i \big| 1\leqslant i\leqslant N$ 且 $dp[i]=1 \big\rbrace$ 引一条容量为 1 的边 - 建立汇点 $t$，从 $\big\lbrace x'\_i \big| 1\leqslant i\leqslant N$ 且 $dp[i]=ans \big\rbrace$ 向 $t$ 引一条容量为 1 的边 跑最大流即可。 3. 在 2. 的基础上，仅需将从源点出发的边及到达汇点的边（不包括反向边）的容量全改为无穷即可

原题描述不严谨，如果第一问答案为 2，第三问中，方案 $\big\lbrace x_1,x_N \big\rbrace$ 只能记做一次。
最后需要注意的是，当 $N=1$ 时，第三问要特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const int MAXN = 400+10;/*{{{*/
const int INF = 0x3f3f3f3f;

int dp[MAXN], in[MAXN];

int main()
{
    int N = read();
    for(int i=1; i <= N; ++i) in[i] = read();

    for(int i=1; i <= N; ++i) 
        for(int j=0; j < i; ++j)
            if( in[i] > in[j] ) 
                dp[i] = std:: max(dp[i], dp[j]+1);

    int ans = 0;
    for(int i=1; i <= N; ++i) ans = std:: max(ans, dp[i]);
    printf("%d\n", ans);

    for(int i=1; i <= N; ++i) { 
        if( dp[i] == 1 ) ISAP:: addedge(0, i<<1, INF);
        ISAP:: addedge(i<<1, i<<1|1, 1);
        if( dp[i] == ans ) ISAP:: addedge(i<<1|1, 1, INF);
    }

    for(int i=1; i <= N; ++i) 
        for(int j=i+1; j <= N; ++j)
            if( in[i] < in[j] && dp[i]+1 == dp[j] )
                ISAP:: addedge(i<<1|1, j<<1, 1);

    ISAP:: s = 0;
    ISAP:: t = 1;
    ISAP:: n = N+1<<1;

    printf("%d\n", ISAP:: maxflow());

    if( ans == 1 ) {
        printf("%d\n", N);
        return 0;
    }

    for(auto& e: ISAP:: edges) e.flow = 0;
    for(auto& i: ISAP:: G[2]) {
        auto& e = ISAP:: edges[i];
        if( e.to == 3 ) { 
            e.cap = INF;
            break;
        }
    }

    for(auto& i: ISAP:: G[N<<1]) {
        auto& e = ISAP:: edges[i];
        if( e.to == (N<<1|1) ) {
            e.cap = INF;
            break;
        }
    }

    printf("%d\n", ISAP:: maxflow());

    return 0;
}/*}}}*/

07

**COGS/732 *[试题库](http://cojs.tk/cogs/problem/problem.php?pid=732)*** 如 **[05](#05)**，经典的二分图多重匹配问题。 - 将每道题与其所属类型连接一条容量为 1 的边 - 建立源点 $s$，从 $s$ 向每道试题引一条容量为 1 的边 - 建立汇点 $t$，从每个类型向 $t$ 引一条容量为该类型所需要的题数的边

跑最大流，仅当流量为所有类型所需要的题数总和时有解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void ISAP:: solve(int K, int N, int limit) {/*{{{*/
    s = 0; t = N+K+1; n = N+K+2;
    if( maxflow() != limit ) { puts("NoSolution!"); return ; } 
    for(int o=1; o <= K; ++o) {
        printf("%d:", o);
        for(int i=0; i < G[N+o].size(); ++i) {
            edge& e = edges[G[N+o][i]];
            if( e.to <= N && e.flow == -1 ) printf(" %d", e.to);
        }
        putchar('\n');
    }
}
 
const int MAXN = 400+10;
const int INF = 0x3f3f3f3f;
 
int main()
{
freopen("testlib.in", "r", stdin);
freopen("testlib.out", "w", stdout);
    int K = read();
    int N = read();
    int limit = 0;
    
    for(int i=1; i <= K; ++i) {
        int val = read();
        limit += val;
        ISAP:: addedge(N+i, N+K+1, val);
    }
 
    for(int i=1; i <= N; ++i) {
        ISAP:: addedge(0, i, 1);
        int M = read();
        while( M-- ) {
            int j = read();
            ISAP:: addedge(i, N+j, 1);
        }
    }
 
    ISAP:: solve(K, N, limit); 
    return 0;
}/*}}}*/

08

**Power OJ/1743 *[机器人路径规划问题](https://www.oj.swust.edu.cn/problem/show/1743)*** **暂缺**

09

**Power OJ/1744 *[方格取数问题](https://www.oj.swust.edu.cn/problem/show/1744)*** 经典的二分图点权最大独立集。 将方格二染色得到二分图 - 对于左侧的点，向其对应方格的前后左右方格对应的点连接一条容量为$\infty$的边 - 建立源点 $s$，从 $s$ 向左侧的点分别引一条`容量为该点所对应的方格中的数`的边 - 建立汇点 $t$，从右侧的点分别引一条`容量为该店所对应的方格中的数`的边

跑最大流，方格中的数的和 - 最大流量 即是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int INF = 0x3f3f3f3f;/*{{{*/

int main()
{
    int row = read();
    int col = read();
    int tot = 0;
    int idx = 0;

    for(int r=1; r <= row; ++r)
        for(int c=1; c <= col; ++c) {
            ++idx;
            int val = read();
            tot += val;
            if( (r+c) & 1 ) ISAP:: addedge(idx, row*col+1, val);
            else {
                ISAP:: addedge(0, idx, val);
                if( c > 1 ) ISAP:: addedge(idx, idx-1, INF);
                if( r > 1 ) ISAP:: addedge(idx, idx-col, INF);
                if( c < col ) ISAP:: addedge(idx, idx+1, INF);
                if( r < row ) ISAP:: addedge(idx, idx+col, INF);
            }
        }

    ISAP:: s = 0;
    ISAP:: t = row*col + 1;
    ISAP:: n = row*col + 2;

    printf("%d\n", tot - ISAP:: maxflow());
    return 0;
}/*}}}*/

10

**Power OJ/1745 *[餐巾计划问题](https://www.oj.swust.edu.cn/problem/show/1745)*** 最小费用最大流。 设第 $i$ 天有 $A\_i$ 条脏毛巾（可以是之前的脏毛巾累积下来的），需要 $B\_i$ 条干净的毛巾。 将第 $i$ 天拆成两个点 $\alpha\_i$，$\beta\_i$。 - 建立源点 $s$ * 从 $s$ 向 $\alpha\_i$ 引一条容量为 $B\_i$、`单位流量费用为 0`的边（表示每天会产生 $B\_i$ 条脏毛巾） * 从 $s$ 向 $\beta\_i$ 引一条容量为 $B\_i$（或者大于等于 $B\_i$ 皆可）、`单位流量费用为新毛巾的费用`的边（表示每天可以购买的新毛巾数） - 建立汇点 $t$ * 从 $\beta\_i$ 向 $t$ 引一条容量为 $B\_i$、`单位流量费用为 0` 的边（表示每天需要的干净的毛巾数） - 如果 $i+m+1 \leqslant j$（此 OJ 本题数据有点不一样，应为 $i+m \leqslant j$），那么从 $A\_i$ 向 $B\_j$ 引一条容量为 $\infty$（大于 $\displaystyle \sum\_{k=1}^i B\_k$ 即可）、单位流量费用为 $f$ 的边（表示第 $i$ 天快洗可以提供给第 $j$ 天；这里有这样一个事实：如果第 $j+k$ 天需要用到快洗的毛巾，那么大可以将脏毛巾攒到第 $i+k$ 天快洗） - 慢细连边类似 - 最后，对于 $i < N$，从 $A\_i$ 向 $A\_{i+1}$ 引一条容量为 $\infty$、`单位流量费用为 0` 的边（表示每天留下来的脏毛巾可以免费留到第二天洗）

跑最小费用最大流即可，由于每天新毛巾可以直接供应 $B_i$ 条，因此必然可以满流。最小费用即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int INF = 0x3f3f3f3f;/*{{{*/

int main()
{
    int N = read();
    int p = read();
    int m = read();
    int f = read();
    int n = read();
    int s = read();

    MCMF:: init(0, 1);
    for(int i=1; i <= N; ++i) {
        int val = read();
        MCMF:: addedge(0, i<<1, val, 0);
        MCMF:: addedge(0, i<<1|1, val, p);
        MCMF:: addedge(i<<1|1, 1, val, 0);
        if( i+1 <= N ) MCMF:: addedge(i<<1, (i+1)<<1, INF, 0);
        if( i+m <= N ) MCMF:: addedge(i<<1, (i+m)<<1|1, INF, f);
        if( i+n <= N ) MCMF:: addedge(i<<1, (i+n)<<1|1, INF, s);
    }

    std:: pair<int, int> ans = MCMF:: mincostmaxflow();

    printf("%d\n", ans.second);
    return 0;
}/*}}}*/

11

**Power OJ/1746 *[航空路线问题](https://www.oj.swust.edu.cn/problem/show/1746)*** 最大费用最大流。 其实是求两条最长的不相交路径。 - 为了保证每个城市只访问一次，需要拆点；不妨将第 $i$ 个城市拆成 $\alpha\_i$ 和 $\beta\_i$，且从 $\alpha\_i$ 向 $\beta\_i$ 引一条容量为 1，费用为 1 的边 - 如果 $i < j$ 且城市 $i$ 和 城市 $j$ 之间有直达航线，那么向 $\beta\_i$ 和 $\alpha\_j$ 连接一条容量为 1，费用为 0 的边

跑最大费用最大流（只增广两次），方案根据满流边判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>/*{{{*/

namespace MCMF {
    const int MAXN = 1000+10;
    const int INF = 0x3f3f3f3f;

    struct edge {
        int from, to, cap, flow, cost;
        edge(int from=0, int to=0, int cap=0, int flow=0, int cost=0):
            from(from), to(to), cap(cap), flow(flow), cost(cost) {}
    }; 

    int s, t;
    int path[MAXN];
    int dist[MAXN];
    std:: vector<edge> edges;
    std:: vector<int> G[MAXN];

    void addedge(int from, int to, int cap, int cost) {
        int siz = edges.size();
        edges.push_back(edge(from, to, cap, 0, cost));
        edges.push_back(edge(to, from, 0, 0, -cost));
        G[from].push_back(siz);
        G[to].push_back(siz+1);
    }

    bool SPFA() {
        static std:: queue<int> Q;
        static bool inq[MAXN];

        memset(dist, 0x3f, sizeof dist);
 
        Q.push(s);
        inq[s] = true;
        dist[s] = 0;
 
        while( !Q.empty() ) {
            int o = Q.front(); Q.pop();
            for(int i=0; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( e.cap > e.flow && dist[e.to] > dist[o]+e.cost ) {
                    dist[e.to] = dist[o] + e.cost;
                    path[e.to] = G[o][i];
                    if( inq[e.to] ) continue;
                    inq[e.to] = true;
                    Q.push(e.to);
                }
            }
            inq[o] = false;
        }
 
        return dist[t] != INF;
    }

    void DFS(std:: vector<int>& ans, int o) {
        ans.push_back(o>>1);
        for(auto& i: G[o]) {
            edge& e = edges[i];
            if( e.flow == 1 ) DFS(ans, e.to|1);
        }
    }

    bool solve(std:: string* in) {
        static std:: vector<int> ans[2];
        for(int i=0; i < 2; ++i) {
            if( !SPFA() ) return false;
            for(int o = t; o != s;) {
                edges[path[o]].flow += 1;
                edges[path[o]^1].flow -= 1;
                o = edges[path[o]].from;
            }
        }

        for(auto& i: G[3]) {
            edge& e = edges[i];
            if( e.flow == 2 ) {
                printf("%d\n", 2);
                std:: cout << in[1] << "\n" << in[t>>1] << "\n" << in[1] << "\n";
                return true;
            }
        }

        ans[0].push_back(s>>1);
        ans[1].push_back(s>>1);
        int idx = 0;
        for(auto& i: G[3]) {
            edge& e = edges[i];
            if( e.flow == 1 ) {
                DFS(ans[idx++], e.to|1);
            }
        }

        ans[1].pop_back();
        std:: reverse(ans[1].begin(), ans[1].end());
        printf("%d\n", ans[0].size() + ans[1].size()-1);
        for(auto& a: ans[0]) std:: cout << in[a] << "\n";
        for(auto& a: ans[1]) std:: cout << in[a] << "\n";
        return true;
    }
};

inline int read() {
    bool positive = true;
    char c = getchar();
    int s = 0;
    for(; c < '0' || c > '9'; c=getchar())
        if( c == '-' ) positive = false;
    for(; c >= '0' && c <= '9'; c=getchar())
        s = s*10 + c-'0';
    return positive? s: -s;
}

const int MAXN = 100+10;
const int INF = 0x3f3f3f3f;
std:: unordered_map<std:: string, int> ump;
std:: string in[MAXN];

int main()
{
    int N = read();
    int M = read();
    for(int i=1; i <= N; ++i) {
        std:: cin >> in[i];
        ump[in[i]] = i;
        if( i == 1 || i == N ) MCMF:: addedge(i<<1, i<<1|1, 2, -1);
        else MCMF:: addedge(i<<1, i<<1|1, 1, -1);
    }

    for(int i=1; i <= M; ++i) {
        std:: string s, t;
        std:: cin >> s >> t;
        int ids = ump[s];
        int idt = ump[t];
        if( ids > idt ) std:: swap(ids, idt);
        if( ids == 1 && idt == N ) MCMF:: addedge(ids<<1|1, idt<<1, 2, 0);
        else MCMF:: addedge(ids<<1|1, idt<<1, 1, 0);
    }

    MCMF:: s = 1<<1;
    MCMF:: t = N<<1|1;
    if( !MCMF:: solve(in) ) puts("No Solution!");
    return 0;
}/*}}}*/

12

**Power OJ/1747 *[软件补丁问题](https://www.oj.swust.edu.cn/problem/show/1747)*** 更像一个状压 $dp$。 抽象出图的结构，跑最短路即可。 定义 $s$ 为当前软件的错误状态，如果 $s$ 中包含 $B1[i]$ 的所有错误，且不包含 $B2[i]$ 中的所有错误，那么存在一条从 $s$ 到 $s-F1[i]+F2[i]$（这里的‘-’指集合运算），且花费为 $cost[i]$ 的边。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>/*{{{*/

namespace solve {
    const int INF = 0x3f3f3f3f;
    const int MAXN = (1<<20) + 10;

    struct node {
        int B1, B2;
        int F1, F2;
        int cost;
        node(int B1=0, int B2=0, int F1=0, int F2=0, int cost=0):
            B1(B1), B2(B2), F1(F1), F2(F2), cost(cost) {}
    };

    int s, t;
    int dist[MAXN];
    std:: vector<node> nodes;
    
    void update(char* s, int& x, int& y) {
        x = y = 0;
        for(int i=0; s[i]; ++i) {
            if( s[i] == '+' ) x |= 1<<i;
            else if( s[i] == '-' ) y |= 1<<i;
        }     
    }

    int SPFA() {
        static bool inq[MAXN];
        static std:: queue<int> Q; 

        memset(dist, 0x3f, sizeof dist);

        Q.push(s);
        dist[s] = 0;
        inq[s] = true;

        while( !Q.empty() ) {
            int o = Q.front(); Q.pop();
            for(auto& e: nodes) {
                if( (o&e.B1) == e.B1 && (o&e.B2) == 0 ) {
                    int u = (o&e.F1) | e.F2;
                    if( dist[u] > dist[o]+e.cost ) {
                        dist[u] = dist[o]+e.cost;
                        if( !inq[u] ) {
                            inq[u] = true;
                            Q.push(u);
                        }
                    }
                }
            }
            inq[o] = false;
        }
        
        return dist[t] != INF? dist[t]: 0;
    }

};

inline int read() {
    bool positive = true;
    char c = getchar();
    int s = 0;
    for(; c < '0' || c > '9'; c=getchar())
        if( c == '-' ) positive = false;
    for(; c >= '0' && c <= '9'; c=getchar())
        s = s*10 + c-'0';
    return positive? s: -s;
}

int main()
{
    int N = read();
    int M = read();
    int B1, B2, F1, F2, cost, re;
    char in[100];

    re = (1<<N)-1;
    for(int i=0; i < M; ++i) {
        cost = read();
        scanf("%s", in);
        solve:: update(in, B1, B2);
        scanf("%s", in);
        solve:: update(in, F2, F1);
        F1 = re^F1;
        solve:: nodes.push_back(solve:: node(B1, B2, F1, F2, cost));
    }

    solve:: s = re;
    solve:: t = 0;
    printf("%d\n", solve:: SPFA());
    
    return 0;
}/*}}}*/

汇总

problems categories solution code
Power OJ/1736 二分图最大匹配 01 Code
Power OJ/1737 最大权闭合图 02 Code
Power OJ/1738 最小路径覆盖 03 Code
Power OJ/1739 最小路径覆盖 04 Code
Power OJ/1740 二分图多重匹配 05 Code
Power OJ/1741 最多最长不相交路径 06 Code
COGS/732 二分图多重匹配 07 Code
Power OJ/1743 暂缺 08 暂缺
Power OJ/1744 二分图点权最大独立集 09 Code
Power OJ/1745 最小费用最大流（难在建图） 10 Code
Power OJ/1746 最大费用最大流 11 Code