学习参考

  1. [教程]网络流详解: 从入门到放弃

  2. [网络流]学习笔记：一次理解网络流！

  3. Dinic算法

最大流问题

圆桌问题

题目链接：luogu - 3254

题意：有来自m个不同单位的代表参加一次国际会议，第i个单位派出了$r_{i}$个代表，会议的餐厅共有n张餐桌，第i张餐桌可容纳$c_{i}$个代表就餐，为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐，请给出一个满足要求的代表就餐方案

思路：二分图的最大流问题，m个单位是一种点，n张餐桌是另一种点，而代表就是流量，我们从源点s连接一条容量为$r_{i}$的边到第i个单位，然后再从第i个餐桌连接一条容量为$c_{i}$的边到t，这样就保证了 第i个单位派出了$r_{i}$个代表和第i张餐桌可容纳$c_{i}$个代表就餐 这两个条件，我们再在每个单位和餐桌之间连一条容量为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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w;
};

Edge edge[2 * N];
int n, m, cnt, s, t;
int head[N], d[N], cur[N];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 1; i <= t; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

int main()
{
    init();
    scanf("%d%d", &m, &n);
    int sum = 0;
    s = n + m + 1, t = n + m + 2;
    for (int i = 1; i <= m; i++) {
        int x;
        scanf("%d", &x);
        sum += x;
        add_edge(s, i, x);
        add_edge(i, s, 0);
    }
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        add_edge(m + i, t, x);
        add_edge(t, m + i, 0);
    }
    for (int i = 1; i <= m; i++) {
        for (int k = m + 1; k <= m + n; k++) {
            add_edge(i, k, 1);
            add_edge(k, i, 0);
        }
    }
    int res = dinic();
    if (res != sum) {
        printf("0\n");
        return 0;
    }
    printf("1\n");
    for (int u = 1; u <= m; u++) {
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (v != s && 0 == w) printf("%d ", v - m);
        }
        printf("\n");
    }
    return 0;
}

飞行员配对方案问题

题目链接：luogu - 2756

题意：英国皇家空军从沦陷国征募了大量外籍飞行员，由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员，其中1名是英国飞行员，另1名是外籍飞行员，在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合，皇家空军共有n名英国飞行员，m名为外籍飞行员。对于给定的外籍飞行员与英国飞行员的配合情况，问皇家空军一次最多能派出多少架飞机

思路：二分图最大流问题，外籍飞行员是一种点，英国飞行员是另一种点，从源点连接一条容量为1的边到外籍飞行员，从英国飞行员连接一条容量为1的边到汇点，再将能够互相配合的飞行员之间连一条容量为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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 10010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w;
};

int m, n, cnt, s, t;
int d[N], cur[N], head[N];
Edge edge[2 * N];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 1; i <= t; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

int main()
{
    init();
    scanf("%d%d", &m, &n);
    s = n + m + 1, t = s + 1;
    int u, v;
    while (scanf("%d%d", &u, &v) && -1 != u && -1 != v) {
        add_edge(u, v, 1);
        add_edge(v, u, 0);
    }
    for (int i = 1; i <= m; i++) {
        add_edge(s, i, 1);
        add_edge(i, s, 0);
    }
    for (int i = m + 1; i <= n + m; i++) {
        add_edge(i, t, 1);
        add_edge(t, i, 0);
    }
    int res = dinic();
    printf("%d\n", res);
    for (int u = 1; u <= m; u++) {
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (v == s) continue;
            if (0 == w) printf("%d %d\n", u, v);
        }
    }
    return 0;
}

家园 / 星际转移问题

题目连接：luogu - 2754

题意：现有n个太空站位于地球与月球之间，且有m艘太空船在其间来回穿梭，每个太空站可容纳无限多的人，而第i艘太空船只可容纳h[i]个人，每艘太空船将周期性地停靠一系列的太空站，每一艘太空船从一个太空站驶往任一太空站耗时均为 1，人们只能在太空船停靠太空站(或月球、地球)时上、下船，初始时所有人全在地球上，太空船全在初始站，问让k个人全部转移到月球上的最少天数

思路：按照时间分层，从源点向每天的地球连接一条容量为INF的边，从每天的月球向汇点连接一条容量为INF的边，从上一天的第i个节点向今天的第i个节点连接一条容量为INF的边(因为乘客可以在某个空间站停留，此时位置不变)，针对每一艘太空船，找到上一天太空船的位置x，以及这一天太空船的位置y，连接一条容量为h[i]的边从x到y，表示乘客乘坐太空船转移，然后每天增加一些边，跑最大流，直到转移的人数大于k

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 100010;
const int M = 110;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w;
};

Edge edge[2 * N];
int n, m, s, t, k, cnt;
int d[N], cur[N], head[N];
int h[M], r[M], sp[M][M];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 0; i < N; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

void insert(int u, int v, int w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}

int main()
{
    init();
    scanf("%d%d%d", &n, &m, &k);
    n += 2;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &h[i], &r[i]);
        for (int j = 0; j < r[i]; j++) {
            scanf("%d", &sp[i][j]);
            sp[i][j] += 2;
        }
    }
    s = N - 2, t = N - 1;
    int sum = 0, res = 0;
    while (res < 500) {
        insert(s, res * n + 2, INF);
        insert(res * n + 1, t, INF);
        if (0 != res) {
            for (int i = 1; i <= n; i++)
                insert((res - 1) * n + i, res * n + i, INF);
            for (int i = 1; i <= m; i++) {
                int x = sp[i][(res - 1) % r[i]];
                int y = sp[i][res % r[i]];
                insert((res - 1) * n + x, res * n + y, h[i]);
            }
        }
        sum += dinic();
        if (sum >= k) break;
        res++;
    }
    printf("%d\n", 500 == res ? 0 : res);
    return 0;
}

Collectors Problem

题目链接：uva - 10779

题意：Bob和他的朋友从糖果包装里收集贴纸，这些朋友每人手里都有一些(可能有重复的)贴纸，并且只跟别人交换他所没有的贴纸，贴纸总是一对一交换，Bob比这些朋友更聪明，因为他意识到指跟别人交换自己没有的贴纸并不总是最优的，在某些情况下，换来一张重复的贴纸会更划算，假设Bob的朋友只和Bob交换(他们之间不交换)，并且这些朋友只会出让手里的重复贴纸来交换它们没有的不同贴纸，你的任务是帮助Bob算出它最终可以得到的不同贴纸的最大数量

思路：分两组点，第一组为贴纸的种类，第二组点为Bob的朋友，从源点s连接一条容量为ci的边到第i种贴纸，表示Bob每种贴纸能交换多少，对于每一个朋友，如果某个朋友没有第i种贴纸，则应该从第i种贴纸连接一条容量为1的边到这个朋友(因为每个朋友不会收集重复的贴纸)，如果某个朋友的第i种贴纸数量c[i]>1，那么他就会用c[i]-1个贴纸与Bob交换，所以还需要从这个朋友连接一条容量为c[i]-1的边到第i种贴纸，最后只需要从每种贴纸处连接一条容量为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
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 10010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w;
};

int T, n, m, cnt, s, t;
int d[N], cur[N], head[N];
int c[15][30], icas;
Edge edge[2 * N];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
    memset(c, 0, sizeof(c));
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 1; i <= t; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

void insert(int u, int v, int w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            int k, x;
            scanf("%d", &k);
            while (k--) {
                scanf("%d", &x);
                c[i][x]++;
            }
        }
        s = 1, t = n + m + 1;
        for (int i = 1; i <= m; i++) {
            if (0 == c[1][i]) continue;
            insert(s, i + n, c[1][i]);
        }
        for (int i = 1; i <= m; i++) insert(i + n, t, 1);
        for (int i = 2; i <= n; i++) {
            for (int k = 1; k <= m; k++) {
                if (0 == c[i][k]) {
                    insert(k + n, i, 1);
                    continue;
                }
                if (1 == c[i][k]) continue;
                insert(i, k + n, c[i][k] - 1);
            }
        }
        int res = dinic();
        printf("Case #%d: %d\n", ++icas, res);
    }
    return 0;
}

最大流与最小割

王者之剑

题目链接：luogu - 4474

题意：这是在阿尔托利亚·潘德拉贡成为英灵前的事情，她正要去拔出石中剑成为亚瑟王，在这之前她要去收集一些宝石，宝石排列在一个n*m的网格中，每个网格中有一块价值为v(i,j)的宝石，阿尔托利亚·潘德拉贡可以选择自己的起点，开始时刻为0秒。以下操作，每秒按顺序执行：

  • 在第i秒开始的时候，阿尔托利亚·潘德拉贡在方格(x,y)上，她可以拿走(x,y)中的宝石
  • 在偶数秒，阿尔托利亚·潘德拉贡周围四格的宝石会消失
  • 若阿尔托利亚·潘德拉贡第i秒开始时在方格(x,y)上，则在第i+1秒可以立即移动到(x+1,y)，(x,y+1)，(x-1,y)或(x,y-1)上，也可以停留在(x,y)上

求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石

思路：由于是从0秒开始，所以选中一个格子后，四周的格子就不能选了，也就是说不能选相邻的点，所以将网格黑白染色后，分成两组点，一组为黑点，一组为白点，s与黑点相连，t与白点相连，边的容量为方格中宝石的价值，与s相连表示选中这个黑点，与t相连表示选中这个白点，我们将黑点与他相邻的白点之间连接一条容量为$\infty$的边，这就意味着只有当s与t不连通时才是合法的，所以对这个图求最小割，由于黑点与他相邻的白点之间有一条$\infty$的边，这条边一定不会出现在最小割中，意味着需要强制割去与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
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 110;
const int M = 100010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w;
};

int n, m, cnt, s, t;
int d[M], cur[M], head[M], c[N][N];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
Edge edge[M];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 1; i <= t; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

void insert(int u, int v, int w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}

int main()
{
    init();
    scanf("%d%d", &n, &m);
    s = n * m + 1, t = s + 1;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) {
            scanf("%d", &c[i][k]);
            sum += c[i][k];
            int p = (i - 1) * m + k;
            if (0 == (i + k) % 2) insert(s, p, c[i][k]);
            else insert(p, t, c[i][k]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) {
            int p = (i - 1) * m + k;
            if (1 == (i + k) % 2) continue;
            for (int j = 0; j < 4; j++) {
                int x = i + dx[j], y = k + dy[j];
                if (x < 1 || x > n || y < 1 || y > m) continue;
                insert(p, (x - 1) * m + y, INF);
            }
        }
    }
    int res = dinic();
    printf("%d\n", sum - res);
    return 0;
}

Number

题目链接：bzoj - 3275

题意：有n个正整数，需要从中选出一些数，使这些数的和最大，若两个数a,b同时满足以下条件，则a,b不能同时被选

  • 存在正整数c，使$a^2+b^2=c^2$
  • gcd(a,b)=1

思路：偶数与偶数是能够同时被选的，因为两个偶数的gcd为2，奇数与奇数也是能够同时被选的，因为两个奇数的平方和在模4的意义下为2，完全平方数在模4的意义下为0或1，所以将n个数分为两组，一组为奇数，另一组为偶数，s与奇数相连，t与偶数相连，边的容量为数的大小，我们将满足两个条件的a,b之间连接一条容量为$\infty$的边，这就意味着只有当s与t不连通时才是合法的，所以对这个图求最小割，由于满足条件的a,b之间有一条$\infty$的边，这条边一定不会出现在最小割中，意味着需要强制割去与s相连和与t相连的边，这时的最小割即表示“最少能抛弃的数”，将n个数的和减去“最少能抛弃的数”即可

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>

using namespace std;

const int N = 3010;
const int M = 100010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w;
};

int n, s, t, cnt;
int d[N], cur[N], head[N], c[N];
Edge edge[M];
queue<int> q;

int gcd(int a, int b)
{
    return 0 == b ? a : gcd(b, a % b);
}

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 1; i <= t; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

void insert(int u, int v, int w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}

bool check(int a, int b)
{
    int c = a * a + b * b, sq = (int)sqrt(c);
    if (sq * sq == c && 1 == gcd(a, b)) return true;
    return false;
}

int main()
{
    init();
    scanf("%d", &n);
    s = n + 1, t = s + 1;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
        sum += c[i];
        if (c[i] & 1) insert(s, i, c[i]);
        else insert(i, t, c[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int k = i + 1; k <= n; k++) {
            if (c[i] % 2 == c[k] % 2) continue;
            if (check(c[i], c[k])) {
                if (1 == c[i] % 2) insert(i, k, INF);
                else insert(k, i, INF);
            }
        }
    }
    int res = dinic();
    printf("%d\n", sum - res);
    return 0;
}
  1. [Ahoi2009]Mincut 最小割

题目链接：bzoj - 1797

题意：A，B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路，设其中第i(1$\leq$i$\leq$M)条道路连接了$v_{i}$,$u_{i}$两个中转站，那么中转站$v_{i}$可以通过该道路到达$u_{i}$中转站，如果切断这条道路，需要代价$c_{i}$，现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小，小可可一眼就看出，这是一个求最小割的问题，但爱思考的小可可并不局限于此，现在他对每条单向道路提出两个问题：

  • 是否存在一个最小代价路径切断方案，其中该道路被切断
  • 是否对任何一个最小代价路径切断方案，都有该道路被切断

思路：跑一遍最小割，然后在残余网络上跑tarjan求出所有的强连通分量(scc)，将每个scc缩成一个点，有以下性质：

  1. 对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当scc[u]!=scc[v]
  2. 对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当scc[u]==scc[s]且scc[v]==scc[t]

证明：对于1，将每个scc缩成一个点后得到新图，新图的每条边都满流，那么新图的任意一个s-t割都对应原图的某个最小割，所以当scc[u]!=scc[v]时，(u,v)能够出现在某个最小割集中

对于2，如果将(u,v)的流量增大，那么就会形成s->u->v->t的通路，于是最大流的流量就会增加，也就相当于增加了最小割的容量，所以(u,v)这条边一定会出现在最小割中

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 200010;
const int M = 500010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int u, to, nex, w;
};

int n, m, s, t, cnt, top, tim, csc;
int d[N], cur[N], head[N];
int st[N], dfn[N], low[N], vis[N], scc[N];
Edge edge[M];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].u = u;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 1; i <= n; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

void insert(int u, int v, int w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}

void tarjan(int u)
{
    st[++top] = u;
    vis[u] = 1;
    dfn[u] = low[u] = ++tim;
    for (int i = head[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (0 == w) continue;
        if (0 == dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        int v = 0;
        csc++;
        while (v != u) {
            v = st[top--];
            scc[v] = csc;
            vis[v] = 0;
        }
    }
}

int main()
{
    init();
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        insert(u, v, w);
    }
    int res = dinic();
    for (int i = 1; i <= n; i++)
        if (0 == dfn[i]) tarjan(i);
    for (int i = 0; i <= cnt; i += 2) {
        if (edge[i].w) {
            printf("0 0\n");
            continue;
        }
        printf("%d ", scc[edge[i].u] != scc[edge[i].to]);
        printf("%d\n", scc[edge[i].u] == scc[s] && scc[edge[i].to] == scc[t]);
    }
    return 0;
}

Firing

题目链接：poj - 2987

题意：给定一个有向图，顶点带权值，你可以选中一些顶点，要求当选中一个点u的时候，若存在边u->v则v也必须选中，求选中的点的最大总权值和选中了多少个点

思路：我们设与s相连的点是被选中的点，与t相连的点是没有选中的点，并且s与权值为正的点相连，当不选一个权值为正的点时，需要付出的代价为val[i]，所以从s连接一条容量为val[i]的边到第i个点，t与权值为负的点相连，当选中一个权值为负的点时，需要付出的代价为-vali，所以从第i个点连接一条容量为-val[i]的边到t，将u和v之间连接一条容量为$\infty$的边，这就意味着只有当s与t不连通时才是合法的，求出最小割后，那么此时最小割表示的是“放弃的点的最小总权值和”，此时残余网络中的节点(除去容量为0的点)表示的就是选中的节点，dfs一遍求出答案即可

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int N = 5010;
const int M = 60010;
const ll INF = 1000000000000000;

struct Edge {
    int to, nex;
    ll w;
};

int n, m, s, t, cnt, vis[N];
int d[N], cur[N], head[N];
ll val[N];
Edge edge[2 * M];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, ll w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

ll dfs(int u, ll dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to;
        ll w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            ll di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs(){
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to;
            ll w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

void dinic()
{
    ll res = 0;
    while (bfs()) {
        for (int i = 1; i <= t; i++) cur[i] = head[i];
        while (ll d = dfs(s, INF)) res += d;
    }
}

void insert(int u, int v, ll w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}

void solve(int u)
{
    vis[u] = 1;
    for (int i = head[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to;
        ll w = edge[i].w;
        if (w > 0 && 0 == vis[v] && v != s && v != t) solve(v);
    }
}

int main()
{
    init();
    scanf("%d%d", &n, &m);
    s = n + 1, t = s + 1;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &val[i]);
        if (val[i] >= 0) {
            insert(s, i, val[i]);
            sum += val[i];
        }
        else insert(i, t, -val[i]);
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        insert(u, v, INF);
    }
    dinic();
    solve(s);
    int tot = 0;
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            tot++;
            res += val[i];
        }
    }
    printf("%d %lld\n", tot, res);
    return 0;
}

[Hnoi2013]切糕

题目链接：bzoj - 3144

题意：经过千辛万苦小A得到了一块切糕，切糕的形状是长方体，小A打算拦腰将切糕切成两半分给小B，出于美观考虑，小A希望切面能尽量光滑且和谐，于是她找到你，希望你能帮她找出最好的切割方案。出于简便考虑，我们将切糕视作一个长P、宽Q、高R的长方体点阵，我们将位于第z层中第x行、第y列上(1$\leq$x$\leq$P,1$\leq$y$\leq$Q,1$\leq$z$\leq$R)的点称为(x,y,z)，它有一个非负的不和谐值v(x,y,z),一个合法的切面满足以下两个条件：

  • 与每个纵轴(一共有P×Q个纵轴)有且仅有一个交点，即切面是一个函数f(x,y)，对于所有1$\leq$x$\leq$P,1$\leq$y$\leq$Q，我们需指定一个切割点f(x,y)，且1$\leq$f(x,y)$\leq$R
  • 切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远，对于所有的 1$\leq$x,x′$\leq$P和1$\leq$y,y′$\leq$Q ，若|x−x′|+|y−y′|=1，则 |f(x,y)−f(x′,y′)|$\leq$D，其中D是给定的一个非负整数

可能有许多切面f满足上面的条件，小A希望找出总的切割点上的不和谐值最小的那个，即$\sum$v(x,y,f(x,y))最小

思路：考虑没有高度限制时，显然可以贪心，但我们考虑最小割的做法，我们对于每个位置(x,y)，我们可以从s开始连一条长度为R链到t，边的容量为位置(x,y)每一层的不和谐值，然后跑一边最小割就是答案，加入高度限制，我们只需要考虑下界即可(上界可以在相邻位置的下界中体现)，我们在位置(x,y)的第i层连一条容量为$\infty$的边到相邻位置的第i-D层，这就意味着，当位置(x,y)选择第i层时，相邻位置选择的层数必须大于等于i-D层，否则整个图将会是连通的，显然不合法，建好图后跑最小割即可，最小割就是最后的答案

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 45;
const int M = 70010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w;
};

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int id[N][N][N], c[N][N][N];
int p, q, r, cnt, s, t, tot, D;
int d[M], cur[M], head[M];
Edge edge[4 * M];
queue<int> qt;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!qt.empty()) qt.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    qt.push(s);
    while (!qt.empty()) {
        int u = qt.front();
        qt.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                qt.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 1; i <= t; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

void insert(int u, int v, int w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}

int main()
{
    init();
    scanf("%d%d%d%d", &p, &q, &r, &D);
    int sum = 0;
    for (int z = 1; z <= r; z++) {
        for (int x = 1; x <= p; x++) {
            for (int y = 1; y <= q; y++) {
                id[x][y][z] = ++tot;
                scanf("%d", &c[x][y][z]);
                sum += c[x][y][z];
            }
        }
    }
    s = tot + 1, t = s + 1;
    for (int x = 1; x <= p; x++) {
        for (int y = 1; y <= q; y++) {
            insert(s, id[x][y][1], INF);
            insert(id[x][y][r], t, c[x][y][r]);
        }
    }
    for (int z = 1; z <= r - 1; z++) {
        for (int x = 1; x <= p; x++) {
            for (int y = 1; y <= q; y++) {
                insert(id[x][y][z], id[x][y][z + 1], c[x][y][z]);
            }
        }
    }
    for (int x = 1; x <= p; x++) {
        for (int y = 1; y <= q; y++) {
            for (int z = D + 1; z <= r; z++) {
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (nx < 1 || ny < 1 || nx > p || ny > q) continue;
                    insert(id[x][y][z], id[nx][ny][z - D], INF);
                }
            }
        }
    }
    int res = dinic();
    printf("%d\n", res);
    return 0;
}

花园的守护之神

题目链接：cogs - 2093

题意：看着正在被上古神兽们摧残的花园，花园的守护之神――小Bug同学泪流满面。然而，OIER不相信眼泪，小bug与神兽们的战争将进行到底！通过google，小Bug得知，神兽们来自遥远的戈壁。为了扭转战局，小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂，由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie，而且可以在同一段小路上投掷多只小xie。每只小Xie可以拖延神兽一个单位的时间。即神兽通过整段路程的总时间，等于没有小xie时他们通过同样路径的时间加上路上经过的所有小路上的小xie数目总和。神兽们是很聪明的。他们会在出发前侦查到每一段小路上的小Xie数目，然后选择总时间最短的路径。小Bug现在很想知道最少需要多少只小Xie，才能使得神兽从戈壁来到花园的时间变长。作为花园中可爱的花朵，你能帮助她吗?

思路：显然不是最短路上边是没有用的，所以我们从s和t各跑一遍单点最短路，分别得到ds和dn数组，对于一条边(u,v,w)，当ds[t]==ds[u]+w+dn[v]或者ds[t]==ds[v]+w+dn[u]时，那么(u,v,w)这条边就会出现在最短路上，我们从u连接一条容量为1的边到v，那么新图上只剩下最短路了，对新图跑一边最小割即可，最小割就是最少需要的数量

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
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
 
using namespace std;
 
typedef long long ll;
 
const int N = 1010;
const int M = 500010;
const ll INF = 1000000000000000000;
 
struct Edge {
    int to, nex;
    ll w;
};
 
struct node {
    int u;
    ll d;
    node() { }
    node(int a, ll b) : u(a), d(b) { }
    friend bool operator < (node a, node b) {
        return a.d > b.d;
    }
};
 
int n, m, s, t, cnt, ut[M], vt[M];
ll ds[N], dn[N], dis[N], wt[M];
Edge edge[2 * M];
int head[N], cur[N], d[N];
queue<int> q;
priority_queue<node> qt;
 
void init()
{
    cnt = 1;
    memset(head, -1, sizeof(head));
}
 
void add_edge(int u, int v, ll w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}
 
ll dfs(int u, ll dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to;
        ll w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            ll di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}
 
int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to;
            ll w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}
 
ll dinic()
{
    ll res = 0;
    while (bfs()) {
        for (int i = 1; i <= n; i++) cur[i] = head[i];
        while (ll t = dfs(s, INF)) res += t;
    }
    return res;
}
 
void dijkstra(int s)
{
    for (int i = 0; i < N; i++) dis[i] = INF;
    dis[s] = 0;
    qt.push(node(s, 0));
    while (!qt.empty()) {
        int u = qt.top().u;
        qt.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to;
            ll w = edge[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                qt.push(node(v, dis[v]));
            } 
        }
    }
}
 
void insert(int u, int v, ll w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}
 
int main()
{
    freopen("greendam2002.in", "r", stdin);
    freopen("greendam2002.out", "w", stdout);
    init();
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%lld", &ut[i], &vt[i], &wt[i]);
        add_edge(ut[i], vt[i], wt[i]);
        add_edge(vt[i], ut[i], wt[i]);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++) ds[i] = dis[i];
    dijkstra(t);
    for (int i = 1; i <= n; i++) dn[i] = dis[i];
    init();
    for (int i = 1; i <= m; i++) {
        if (ds[t] == ds[ut[i]] + wt[i] + dn[vt[i]]) {
            insert(ut[i], vt[i], 1);
        }
        if (ds[t] == ds[vt[i]] + wt[i] + dn[ut[i]]) {
            insert(vt[i], ut[i], 1);
        }
    }
    ll res = dinic();
    printf("%lld\n", res);
    return 0;
}

最小费用最大流

运输问题

题目链接：luogu - 4015

题意：W公司有m个仓库和n个零售商店。第i个仓库有$a_{i}$个单位的货物；第j个零售商店需要$b_{j}$个单位的货物，货物供需平衡，即$\sum_{i=1}^{m}a_{i}=\sum_{j=1}^{n}b_{j}$，从第i个仓库运送每单位货物到第j个零售商店的费用为$c_{ij}$，试求最大费用和最小费用

思路：最小费用很简单，最小费用最大流裸题，对于最大费用，我们重新建图，将费用变为负数，求出此时的最小费用后，再将最小费用取反即是最大费用

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 210;
const int M = 10100;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w, c;
};

int n, m, s, t, cnt, mf, mc;
int f[N], dis[N], pre[N], lst[N];
int head[N], inq[N];
int a[N], b[N], c[N][N];
Edge edge[2 * M];
queue<int> q;

void init()
{
    cnt = -1;
    mf = mc = 0;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w, int c)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].c = c;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int spfa(int s, int t)
{
    memset(dis, INF, sizeof(dis));
    memset(f, INF, sizeof(f));
    memset(inq, 0, sizeof(inq));
    while (!q.empty()) q.pop();
    q.push(s);
    inq[s] = 1, dis[s] = 0, pre[t] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w, c = edge[i].c;
            if (0 == w || dis[v] <= dis[u] + c) continue;
            dis[v] = dis[u] + c;
            pre[v] = u;
            lst[v] = i;
            f[v] = min(f[u], w);
            if (1 == inq[v]) continue;
            inq[v] = 1;
            q.push(v);
        }
    }
    if (-1 == pre[t]) return 0;
    return 1;
}

void mcmf()
{
    while (spfa(s, t)) {
        mf += f[t];
        mc += f[t] * dis[t];
        int now = t;
        while (now != s) {
            edge[lst[now]].w -= f[t];
            edge[lst[now] ^ 1].w += f[t];
            now = pre[now];
        }
    }
}

void insert(int u, int v, int w, int c)
{
    add_edge(u, v, w, c);
    add_edge(v, u, 0, -c);
}

void solve(int k)
{
    init();
    for (int i = 1; i <= n; i++)
        insert(s, i, a[i], 0);
    for (int i = 1; i <= m; i++)
        insert(n + i, t, b[i], 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            insert(i, n + j, INF, k * c[i][j]);
    mcmf();
}

int main()
{
    scanf("%d%d", &n, &m);
    s = n + m + 1, t = s + 1;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &c[i][j]);
    solve(1);
    printf("%d\n", mc);
    solve(-1);
    printf("%d\n", -mc);
    return 0;
}

Transportation

题目链接：hdu - 3667

题意：n个城市由m条有向边连接，要从城市1运输k流量到城市n，每条边有可以运输的流量容量，以及费用系数$w_{i}$，费用系数指该条边的费用为该条边的运输流量x的平方乘以$w_{i}$。即$w_{i}*x^{2}$如果无法运输k流量，输出-1，否则输出从城市1运输k流量到城市n的最小花费

思路：不是线性的最小费用最大流，我们采用拆边发，把容量为c的边拆成c条容量为1的边，每条边的费用为$w_{i}$，$3*w_{i}$，$5*w_{i}\cdots$，这样流量x就可以被拼凑出来，例如，如果x=2，花费为$4*w_i$，就会被拆成$w_i+3*w_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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 1010;
const int M = 40010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w, c;
};

int n, m, s, t, k, cnt, mf, mc;
int f[N], inq[N], pre[N], lst[N];
int dis[N], head[N];
Edge edge[2 * M];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
    memset(pre, 0, sizeof(pre));
    memset(lst, 0, sizeof(lst));
    mc = mf = 0;
    // memset(edge, 0, sizeof(edge));
}

void add_edge(int u, int v, int w, int c)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].c = c;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int spfa(int s, int t)
{
    memset(dis, INF, sizeof(dis));
    memset(f, INF, sizeof(f));
    memset(inq, 0, sizeof(inq));
    while (!q.empty()) q.pop();
    q.push(s);
    inq[s] = 1, dis[s] = 0, pre[t] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w, c = edge[i].c;
            if (0 == w || dis[v] <= dis[u] + c) continue;
            dis[v] = dis[u] + c;
            pre[v] = u;
            lst[v] = i;
            f[v] = min(f[u], w);
            if (1 == inq[v]) continue;
            inq[v] = 1;
            q.push(v);
        }
    }
    if (-1 == pre[t]) return 0;
    return 1;
}

void mcmf()
{
    while (spfa(s, t)) {
        mf += f[t];
        mc += dis[t] * f[t];
        int now = t;
        while (now != s) {
            edge[lst[now]].w -= f[t];
            edge[lst[now] ^ 1].w += f[t];
            now = pre[now];
        }
    }
}

void insert(int u, int v, int w, int c)
{
    add_edge(u, v, w, c);
    add_edge(v, u, 0, -c);
}

int main()
{
    while (scanf("%d%d%d", &n, &m, &k) != EOF) {
        init();
        for (int i = 1; i <= m; i++) {
            int u, v, w, c;
            scanf("%d%d%d%d", &u, &v, &w, &c);
            for (int j = 0; j < c; j++) {
                insert(u, v, 1, w * (2 * j + 1));
            }
        }
        s = n + 1, t = s + 1;
        insert(s, 1, k, 0);
        insert(n, t, k, 0);
        mcmf();
        if (mf != k) {
            printf("-1\n");
            continue;
        }
        printf("%d\n", mc);
    }
    return 0;
}

最长k可重区间集问题

题目链接：luogu - 3358

题意：给定实直线L上n个开区间组成的集合I，和一个正整数k，试设计一个算法，从开区间集合I中选取出开区间集合S$\in$I，使得在实直线L的任何一点x，S中包含点x的开区间个数不超过k。且$\sum_{z\in S}|z|$达到最大，这样的集合S称为开区间集合I的最长k可重区间集，$\sum_{z\in S}|z|$称为最长k可重区间集的长度，对于给定的开区间集合I和正整数k，计算开区间集合I的最长k可重区间集的长度

思路：由于是开区间，我们不用考虑端点的覆盖次数，于是我们对每一个区间，我们从左端点连接一条容量为1，费用为区间长度的边到右端点，从源点到第一个点，第i个点到第i+1个点，最后一个点到汇点之间各连一条容量为k，费用为0的边，左端点到右端点那条容量为1的边可以理解为分流，因为一个点最多被覆盖k次，由于求得是最长的长度，也就是最大费用最大流，所以我们将边的费用取反，跑完最小费用最大流后，再将此时的最小费用取反即可

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int N = 1010;
const int M = 200010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w, c;
};

int n, s, t, k, cnt, mf, mc;
int dis[N], L[N], R[N];
int head[N], f[N], inq[N], pre[N], lst[N];
Edge edge[2 * M];
queue<int> q;
vector<int> alls;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w, int c)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].c = c;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int spfa(int s, int t)
{
    memset(dis, INF, sizeof(dis));
    memset(f, INF, sizeof(f));
    memset(inq, 0, sizeof(inq));
    while (!q.empty()) q.pop();
    q.push(s);
    inq[s] = 1, dis[s] = 0, pre[t] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w, c = edge[i].c;
            if (0 == w || dis[v] <= dis[u] + c) continue;
            dis[v] = dis[u] + c;
            pre[v] = u;
            lst[v] = i;
            f[v] = min(f[u], w);
            if (1 == inq[v]) continue;
            inq[v] = 1;
            q.push(v);
        }
    }
    if (-1 == pre[t]) return 0;
    return 1;
}

void mcmf()
{
    while (spfa(s, t)) {
        mf += f[t];
        mc += f[t] * dis[t];
        int now = t;
        while (now != s) {
            edge[lst[now]].w -= f[t];
            edge[lst[now] ^ 1].w += f[t];
            now = pre[now];
        }
    }
}

void insert(int u, int v, int w, int c)
{
    add_edge(u, v, w, c);
    add_edge(v, u, 0, -c);
}

int get_id(int x)
{
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}

int main()
{
    init();
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &L[i], &R[i]);
        alls.push_back(L[i]);
        alls.push_back(R[i]);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    int len = (int)alls.size();
    s = len + 1, t = s + 1;
    for (int i = 1; i <= n; i++) {
        int idl = get_id(L[i]);
        int idr = get_id(R[i]);
        insert(idl, idr, 1, L[i] - R[i]);
    }
    insert(s, 1, k, 0);
    insert(len, t, k, 0);
    for (int i = 1; i < len; i++) insert(i, i + 1, INF, 0);
    mcmf();
    printf("%d\n", -mc);
    return 0;
}

餐巾计划问题

题目链接：luogu - 1251

题意：一个餐厅在相继的n天里，每天需用的餐巾数不尽相同。假设第i天需要$r_i$块餐巾。餐厅可以购买新的餐巾，每块餐巾的费用为P分，或者把旧餐巾送到快洗部，洗一块需M天，其费用为F分，或者送到慢洗部，洗一块需N天，其费用为S分(S<F)，每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量，试设计一个算法为餐厅合理地安排好n天中餐巾使用计划，使总的花费最小

思路：我们发现每天分为两个阶段：早上和晚上，所以我们将一天拆为早上和晚上两个点，对于快洗的餐巾，我们从第i天的晚上连一条容量为$\infty$、费用为F的边到第i+M天的早上，对于慢洗的餐巾，我们从第i天的晚上连一条容量为$\infty$、费用为S的边到第i+N天的早上，同时，从第i天晚上连一条容量为$\infty$、费用为0的边到第i+1天的晚上，表示延期送洗，我们用s来表示产生餐巾，而t来表示需要餐巾，显然第i天晚上会产生$r_i$块餐巾，所以从s连接一条容量为$r_i$、费用为0的边到第i天的晚上，同时还可以从s处购买餐巾，从s连接一条容量为$\infty$、费用为P的边到第i天早上，最后，从第$i$天早上连接一条容量为$r_i$、费用为0的边到t，表示第i天需要$r_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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;


const int N = 4010;
const int M = 100010;
const ll INF = 1000000000000000000;

struct Edge {
    int to, nex;
    ll w, c;
};

int n, s, t, cnt;
ll mc, dis[N], mf, f[N];
int pre[N], lst[N], head[N], inq[N];
Edge edge[2 * M];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, ll w, ll c)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].c = c;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int spfa(int s, int t)
{
    for (int i = 0; i < N; i++) {
        dis[i] = f[i] = INF;
        inq[i] = 0;
    }
    while (!q.empty()) q.pop();
    q.push(s);
    inq[s] = 1, dis[s] = 0, pre[t] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to;
            ll c = edge[i].c, w = edge[i].w;
            if (0 == w || dis[v] <= dis[u] + c) continue;
            dis[v] = dis[u] + c;
            pre[v] = u;
            lst[v] = i;
            f[v] = min(f[u], w);
            if (1 == inq[v]) continue;
            inq[v] = 1;
            q.push(v);
        }
    }
    if (-1 == pre[t]) return 0;
    return 1;
}

void mcmf()
{
    while (spfa(s, t)) {
        mf += f[t];
        mc += dis[t] * f[t];
        int now = t;
        while (now != s) {
            edge[lst[now]].w -= f[t];
            edge[lst[now] ^ 1].w += f[t];
            now = pre[now];
        }
    }
}

void insert(int u, int v, ll w, ll c)
{
    add_edge(u, v, w, c);
    add_edge(v, u, 0, -c);
}

int main()
{
    init();
    scanf("%d", &n);
    s = 2 * n + 1, t = s + 1;
    for (int i = 1; i <= n; i++) {
        ll x;
        scanf("%lld", &x);
        insert(s, i, x, 0);
        insert(n + i, t, x, 0);
    }
    ll pp, ff, ss;
    int mm, nn;
    scanf("%lld%d%lld%d%lld", &pp, &mm, &ff, &nn, &ss);
    for (int i = 1; i <= n; i++) {
        insert(s, n + i, INF, pp);
        if (i + 1 <= n) insert(i, i + 1, INF, 0);
        if (i + mm <= n) insert(i, i + mm + n, INF, ff);
        if (i + nn <= n) insert(i, i + nn + n, INF, ss);
    }
    mcmf();
    printf("%lld\n", mc);
    return 0;
}