网络流题目

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

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 星际战争 - 洛谷

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

源点向 \(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;
}