网络流题目

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

P2472 蜥蜴 - 洛谷

P2472 蜥蜴 - 洛谷

最大流 考虑将问题转化为最多有几只蜥蜴能逃离。

把柱子的点拆成入点出点两部分，它们间的连边的容量就是柱子的高度（能跳出的次数）。

柱子的出点与所有距离 d 以内的柱子的入点和场外点连容量正无穷的边。

源点和有蜥蜴的柱子的入点连容量为 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
map<PII, PII> p;

void add(PII a, PII b, ll c) {
    if (!p.count(a)) {
        p[a].first = n + 1;
        p[a].second = n + 2;
        n += 2;
    }
    if (!p.count(b)) {
        p[b].first = n + 1;
        p[b].second = n + 2;
        n += 2;
    }
    e[p[a].second].push_back((edge){p[b].first, c, e[p[b].first].size()});
    e[p[b].first].push_back((edge){p[a].second, 0, e[p[a].second].size() - 1});
}

void add(ll a, ll b, ll c) {
    e[a].push_back((edge){b, c, e[b].size()});
    e[b].push_back((edge){a, 0, e[a].size() - 1});
}

void solve() {
    ll ans = 0, r, c, d;
    n = 0;
    s = ++n;
    t = ++n;
    cin >> r >> c >> d;
    string g1[30], g2[30];
    for (ll i = 0; i < r; i++) {
        cin >> g1[i];
    }
    for (ll i = 0; i < r; i++) {
        cin >> g2[i];
    }
    for (ll i1 = 0; i1 < r; i1++) {
        for (ll j1 = 0; j1 < c; j1++) {
            for (ll i2 = -1; i2 <= r; i2++) {
                for (ll j2 = -1; j2 <= c; j2++) {
                    if ((i1 - i2) * (i1 - i2) + (j1 - j2) * (j1 - j2) <=
                        d * d) {
                        add({i1, j1}, {i2, j2}, inf);
                    }
                }
            }
            add(p[{i1, j1}].first, p[{i1, j1}].second, g1[i1][j1] - '0');
            if (g2[i1][j1] == 'L') {
                add(s, p[{i1, j1}].first, 1);
                ans++;
            }
        }
    }
    for (ll i2 = -1; i2 <= r; i2++) {
        for (ll j2 = -1; j2 <= c; j2++) {
            if (i2 == -1 || j2 == -1 || i2 == r || j2 == c) {
                add(p[{i2, j2}].first, t, inf);
            }
        }
    }

    while (bfs()) {
        ans -= dfs(s, inf);
    }
    cout << ans << endl;
}

P3324 星际战争 - 洛谷

P3324 星际战争 - 洛谷

最大流 二分 对护甲值乘一万避免解决小数问题。对时间二分转化为可行性问题。

源点向 \(B_i\) 点连 \(tB_i\) 容量边，\(B_i\) 向可以打的 \(A_i\) 连正无穷容量边，\(A_i\) 向汇点连 \(A_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
ll n, m, sum = 0, a[60], b[60], g[60][60];

void add(ll a, ll b, ll c) {
    e[a].push_back((edge){b, c, e[b].size()});
    e[b].push_back((edge){a, 0, e[a].size() - 1});
}

void build(ll mid) {
    for (ll i = 1; i <= dinicn; i++) {
        e[i].clear();
    }
    dinicn = 0;
    s = ++dinicn;
    t = ++dinicn;
    ll ain[60] = {}, bin[60] = {};
    for (ll i = 1; i <= m; i++) {
        add(s, bin[i] = ++dinicn, mid * b[i]);
    }
    for (ll i = 1; i <= m; i++) {
        for (ll j = 1; j <= n; j++) {
            if (!ain[j]) {
                ain[j] = ++dinicn;
            }
            if (g[i][j]) {
                add(bin[i], ain[j], inf);
            }
        }
    }
    for (ll i = 1; i <= n; i++) {
        add(ain[i], t, a[i]);
    }
}

ll check() {
    ll ans = 0;
    while (bfs()) {
        ans += dfs(s, inf);
    }
    if (ans == sum) {
        return 1;
    }
    return 0;
}

void solve() {
    ll ans = 0, L = 0, R = 1e9;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] *= 10000;
        sum += a[i];
    }
    for (ll i = 1; i <= m; i++) {
        cin >> b[i];
    }
    for (ll i = 1; i <= m; i++) {
        for (ll j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }
    dinicn = 0;
    while (L <= R) {
        ll mid = (L + R) / 2;
        build(mid);
        if (check()) {
            R = mid - 1;
            ans = mid;
        } else {
            L = mid + 1;
        }
    }
    cout << fixed << setprecision(4) << ans * 1.0 / 10000 << endl;
}

车车对撞

题意：在 \(n\times n\) 的网格棋盘上有 \(m\) 个象棋的车，还有 \(k\) 个障碍物。需要求出最少额外需要放置几个障碍物可以使车车不能对撞。

点击查看题解

二分图 最大流 经典边化点、点化边的网络流建模。

首先，只有同一行同一列的车车会对撞，考虑把会对撞的都连线，问题就处在当连线交叉的时候，可以一个障碍物挡住两条线（节省一个障碍物），要考虑放哪些交叉点更优。

我们可以注意到，横着的只会和竖着的对撞，竖着的只会和横着的对撞，所以把一条条连线看成一个个点（相当于要阻止对撞的一对车），然后把连线交叉的点看作两条连线的连边（因为占住这个点同时阻止了两对车）。

（以下的点和边都是建模后的点和边）

这样，我们就建了个图，一条边代表选中这一条边可以同时选中这两个端点，而我们的任务是选中所有点（有的点没连边就只能单独选这一个点），花费（选的次数）最少。而因为上面说的“横着的只会和竖着的对撞，竖着的只会和横着的对撞“，所以这是个天然的二分图。这就是二分图的最小边覆盖问题（选最少的边使得所有点都被覆盖）。我们很少提：最小边覆盖问题，因为可以转化为二分图的最大匹配问题（男女配对，每个点只能被选中一次，最多选多少对），因为没选中的点只能单独自己选（点数-最大匹配=最小边覆盖）。然后这个二分图的最大匹配问题，又等价于二分图的最小点覆盖问题（选最少的点，使得所有边都被覆盖），证明过程很复杂，反正答案相等。

（二分图的最小点覆盖问题与本题无关）

二分图的最大匹配又可以转化为最大流，因为可以左边连超级汇点，右边连超级源点，流量 1，就能保证男女都是 1 个人对 1 个。

P4311 士兵占领 - 洛谷

P4311 士兵占领 - 洛谷

题意：在 \(n\times m\) 的网格棋盘上，有 \(K\) 个障碍，每行每列必须至少放 \(L_i\) 或 \(C_i\) 个士兵，问最少放多少个士兵。

点击查看题解

二分图 最大流 因为和上一题一样，每行只会和每列交叉的点连线，和上一题一样，行列看作点，棋盘格点看作连线（有障碍物就不连），也是个二分图。因为求的是最少，世界上没有最小流，所以需要反一下，考虑先全占满，然后选最多能减掉多少个点。于是源点到行的流量是 \(n-\)每行的障碍数\(-L_i\)（因为至少需要 \(L_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
#include<bits/stdc++.h>

using namespace std;
#define PII pair<int,int>
#define TIII tuple<int,int,int>
#define int long long
//网络流(dinic)

const int N = 305, M = 100 * 100 + 100;
vector<TIII > e[M]; //点，边权，反向边编号
int lev[N], cur[N], ans; //bfs分层，弧优化，最大流
int n, s, t;

int bfs() {
    for (int i = 0; i <= n; i++)lev[i] = -1, cur[i] = 0;
    queue<int> q;
    q.push(s);
    lev[s] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto [y, w, temp2]: e[x]) {
            if (lev[y] == -1 && w > 0) {
                lev[y] = lev[x] + 1;
                q.push(y);
            }
        }
    }
    return lev[t] != -1;
}

int dfs(int x, int flow) {
    if (x == t) {
        return flow;
    }
    for (int &i = cur[x]; i < e[x].size(); i++) {
        auto &[y, w, rev] = e[x][i];
        if (lev[y] == lev[x] + 1 && w > 0) {
            int lim = dfs(y, min(flow, w));
            if (lim > 0) {
                w -= lim;
                std::get<1>(e[y][rev]) += lim;
                return lim;
            }
        }
    }
    return 0;
}

signed main() {
    int nn, mm, kk;
    cin >> nn >> mm >> kk;
    int ml[105];
    int nl[105];
    for (int i = 1; i <= nn; i++) {
        cin >> nl[i];
    }
    for (int i = 1; i <= mm; i++) {
        cin >> ml[i];
    }
    set<PII > zhangai;
    int nsum[nn + 1] = {};
    int msum[mm + 1] = {};
    for (int i = 1; i <= kk; i++) {
        int x, y;
        cin >> x >> y;
        zhangai.insert({x, y});
        nsum[x]++;
        msum[y]++;
    }
    s = nn + mm + 1;
    t = nn + mm + 2;
    for (int i = 1; i <= nn; i++) {
        int x = s, y = i, w = mm - nl[i] - nsum[i];
        if (w < 0) {
            cout << "JIONG!";
            return 0;
        }
        e[x].push_back({y, w, e[y].size()});
        e[y].push_back({x, 0, e[x].size() - 1});
    }
    for (int j = 1; j <= mm; j++) {
        int x = j + nn, y = t, w = nn - ml[j] - msum[j];
        if (w < 0) {
            cout << "JIONG!";
            return 0;
        }
        e[x].push_back({y, w, e[y].size()});
        e[y].push_back({x, 0, e[x].size() - 1});
    }
    n = nn + mm + 2;
    for (int i = 1; i <= nn; i++) {
        for (int j = 1; j <= mm; j++) {
            if (zhangai.contains({i, j})) { continue; }
            int x = i, y = j + nn, w = 1;
            e[x].push_back({y, w, e[y].size()});
            e[y].push_back({x, 0, e[x].size() - 1});
        }
    }
    while (bfs()) {
        while (1) {
            int x = dfs(s, 4e18);
            if (x == 0)break;
            ans += x;
        }
    }
    cout << nn * mm - ans - kk;
    return 0;
}

P3191 [HNOI2007] 紧急疏散

P3191 紧急疏散（EVACUATE） - 洛谷

最大流 二分 最短路 可以预处理出每个空地到每个门的最短路，之所以不只找最近的门是因为可能会有门“排长队”反而不优。

然后这种最优问题的一个常见解决方法就是二分需要的时间然后判断是否可行。

于是我们就考虑建图，但是一个问题是一秒只能有一个人进门处理很麻烦，所以考虑对门按时间拆点。

  • 每个门拆出的点对下一时刻连容量无限边来模拟人们“等待”排队。
  • 每个门拆出的点对汇点连一条容量为 1 的边来模拟每秒只能一秒只能有一个人进门。

接着让每个空地向每个能在当前限制时间内到达的门的对应时刻连容量为无限的边。最后从源点向每个空地连边图就建好了。最大流如果等于总人数就是能在限制时间内让所有人逃出。

有一个错误做法：二分同上，源点向所有空地连 1 容量边，空地之间连容量无限边，门旁的空地向门连容量为二分出来的时间边。这个做法正确的前提是认为门从第一时刻就有人进，且之后每一时刻都有人进入直到某时刻停止。而这个前提并不满足。很有格调的 Hack 如下：

1
2
3
XDXXXXXX
X......X
XDXXXXXX

最后一个人到达门显然需要 6 秒，而错误做法认为本样例答案为 3。

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
ll n, m, cnt = 0, f[505][505];
string g[30];
map<PII, ll> p, d, ip;

void add(ll a, ll b, ll c) {
    // cout << "<" << a << ", " << b << ">" << endl;
    e[a].push_back((edge){b, c, e[b].size()});
    e[b].push_back((edge){a, 0, e[a].size() - 1});
}

const ll nx[] = {0, 1, -1, 0, 0};
const ll ny[] = {0, 0, 0, 1, -1};

void build(ll mid) {
    for (ll i = 1; i <= dinicn; i++) {
        e[i].clear();
    }
    p.clear();
    d.clear();
    dinicn = 0;
    s = ++dinicn;
    t = ++dinicn;
    for (ll i = 0; i <= n - 1; i++) {
        for (ll j = 0; j <= m - 1; j++) {
            if (g[i][j] == 'D') {
                p[{i, j}] = ++dinicn;
                for (ll k = 1; k <= mid; k++) {
                    d[{p[{i, j}], k}] = ++dinicn;
                    add(d[{p[{i, j}], k}], t, 1);
                    if (k >= 2) {
                        add(d[{p[{i, j}], k - 1}], d[{p[{i, j}], k}], inf);
                    }
                }
                for (ll ni = 0; ni <= n - 1; ni++) {
                    for (ll nj = 0; nj <= m - 1; nj++) {
                        if (g[ni][nj] == '.' &&
                            f[ip[{ni, nj}]][ip[{i, j}]] <= mid) {
                            if (!p.count({ni, nj})) {
                                p[{ni, nj}] = ++dinicn;
                                add(s, p[{ni, nj}], 1);
                            }
                            add(p[{ni, nj}],
                                d[{p[{i, j}], f[ip[{ni, nj}]][ip[{i, j}]]}], 1);
                        }
                    }
                }
            }
        }
    }
}

ll check() {
    ll ret = 0;
    while (bfs()) {
        ret += dfs(s, inf);
    }
    return ret;
}

void init() {
    ll index = 0;
    for (ll i = 0; i <= n - 1; i++) {
        for (ll j = 0; j <= m - 1; j++) {
            if (g[i][j] == '.') {
                cnt++;
            }
            if (g[i][j] != 'X') {
                ip[{i, j}] = ++index;
            }
        }
    }
    for (ll i = 1; i <= index; i++) {
        for (ll j = 1; j <= index; j++) {
            if (i == j) {
                f[i][j] = 0;
            } else {
                f[i][j] = inf;
            }
        }
    }
    for (ll i = 0; i <= n - 1; i++) {
        for (ll j = 0; j <= m - 1; j++) {
            if (ip.count({i, j})) {
                for (ll k = 1; k <= 4; k++) {
                    ll ni = i + nx[k], nj = j + ny[k];
                    if (ip.count({ni, nj})) {
                        f[ip[{i, j}]][ip[{ni, nj}]] = 1;
                        f[ip[{ni, nj}]][ip[{i, j}]] = 1;
                    }
                }
            }
        }
    }
    for (ll k = 1; k <= index; k++) {
        for (ll i = 1; i <= index; i++) {
            for (ll j = 1; j <= index; j++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
}

void solve() {
    dinicn = 0;
    cin >> n >> m;
    for (ll i = 0; i <= n - 1; i++) {
        cin >> g[i];
    }
    init();
    ll L = 0, R = 10000, ans = -1;
    while (L <= R) {
        ll mid = (L + R) / 2;
        build(mid);
        if (check() == cnt) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    if (ans == -1) {
        cout << "impossible" << endl;
        return;
    }
    cout << ans << endl;
}

P5038 [SCOI2012] 奇怪的游戏

P5038 奇怪的游戏 - 洛谷

最大流 二分 二分图

因为这题是二维棋盘，每次都令相邻格子同时加一，而相邻格子坐标和的奇偶性不同，所以可以看成每次操作为连边，从而形成一个二分图（黑白染色）。

设黑点的个数有 \(B\) 个，权值总和为 \(b\)，白点的个数有 \(W\) 个，权值总和为 \(w\) 。

对于每次操作，因为是选择相邻的两个节点，所以黑点白点肯定各有一个被操作，即 \(b\) 和 \(w\) 各加一。

设最后全部数字都变成 \(X\) ，那么就会有有 \(BX−b=WX−w\) （等于操作的次数）。

这个方程提出了必要条件。如果 \(B\not=W\)，可解出 \(X\)，只需要验证 \(X\) 即可。

如果 \(B=W\)，如果一个 \(X\) 可行，那么我们可以铺满整个棋盘，使整个棋盘的所有数都加上一，即 \(X+1\) 也可行。所以必定存在最小的 \(X'\) 可行，二分这个 \(X\) 验证即可（\(X\) 越大答案也越大）。

验证方法为：黑点连源点，白点连汇点，容量为此点需要被加的次数。黑点与周围白点连边，容量无穷大，表示需要一起被加。最后跑最大流看是不是满流。

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
const ll nx[] = {0, 1, -1, 0, 0};
const ll ny[] = {0, 0, 0, 1, -1};

ll n, m, a[50][50], Flag;

void build(ll x) {
    dinicn = n * m + 2;
    for (ll i = 1; i <= dinicn; i++) {
        e[i].clear();
    }
    s = n * m + 1;
    t = n * m + 2;
    Flag = 0;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            if ((i + j) % 2 == 0) {
                add(s, (i - 1) * m + j, x - a[i][j]);
                Flag += x - a[i][j];
            } else {
                add((i - 1) * m + j, t, x - a[i][j]);
            }
        }
    }
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            if ((i + j) % 2 == 0) {
                for (ll k = 1; k <= 4; k++) {
                    ll i2 = i + nx[k], j2 = j + ny[k];
                    if (i2 >= 1 && i2 <= n && j2 >= 1 && j2 <= m) {
                        add((i - 1) * m + j, (i2 - 1) * m + j2, inf);
                    }
                }
            }
        }
    }
}

ll check() {
    ll ret = 0;
    while (bfs()) {
        ret += dfs(s, inf);
    }
    if (ret == Flag) {
        return 1;
    }
    return 0;
}

void solve() {
    ll B0 = 0, W1 = 0, b0 = 0, w1 = 0, ans = -1, mx = 0;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            cin >> a[i][j];
            mx = max(mx, a[i][j]);
            if ((i + j) % 2 == 0) {
                B0++;
                b0 += a[i][j];
            } else {
                W1++;
                w1 += a[i][j];
            }
        }
    }
    if (B0 != W1) {
        build((b0 - w1) / (B0 - W1));
        if (check()) {
            cout << Flag << endl;
        } else {
            cout << -1 << endl;
        }
    } else {
        ll l = mx, r = 3e9;
        while (l <= r) {
            ll mid = (l + r) / 2;
            build(mid);
            if (check()) {
                ans = Flag;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        cout << ans << endl;
    }
}