題目： UVa - 11380 - Down Went The Titanic

題目說明

給定一個圖，上面有薄冰 ‘.’ 或 ‘*‘, 厚冰 ‘@’, 木塊 ‘#’，一開始人都在 ‘*‘ 上，薄冰只能走一次就會沉掉，厚冰次數不限，如果人走到木塊上就獲救了，但是一個木塊的容量只有 p，求最多能有多少人獲救。

UVA 11380 - Down Went The Titanic（网络流）_Remilia’s-CSDN博客

解題思路

最大流，依照上面的說明建邊後使用 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
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
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define CLR(c) memset(c, 0, sizeof(c))

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

template <typename T>
T QPOP(queue<T>& q)
{
    T tmp = q.front();
    q.pop();
    return tmp;
}

// reference: https://ppt.cc/fKhjIx

const int INF = (int)1e9;
const int MXN = 2005;

int S, T;
int rn[MXN][MXN];
int l[MXN];

int Y, X, P;
int tot;
int d[] = { 1, 0, -1, 0, 1 };

void init()
{
    CLR(rn);
}

void read()
{
    tot = Y * X;
    T = 2 * tot + 1;

    char c;
    FOR(y, 0, Y) FOR(x, 0, X)
    {
        int u = X * y + x + 1;
        cin >> c;
        
        switch (c)
        {
        case '*': // 有人
            rn[u][u + tot] = 1;
            rn[S][u] = 1;
            break;

        case '.': // 薄冰
            rn[u][u + tot] = 1;
            break;

        case '@': // 厚冰
            rn[u][u + tot] = INF;
            break;

        case '#':
            rn[u][u + tot] = INF;
            rn[u + tot][T] = P;
            break;
        }

        FOR(i, 0, 4)
        {
            int dx = x + d[i];
            int dy = y + d[i + 1];
            if (dx < 0 || dx >= X || dy < 0 || dy >= Y) continue;

            int v = X * dy + dx + 1;
            rn[u + tot][v] = INF;
        }
    }
}

bool dinicBFS()
{
    CLR(l);

    queue<int> q;
    q.push(S);
    l[S] = 1;

    while (!q.empty())
    {
        int u = QPOP(q);

        FOR(v, 0, T + 1)
        {
            if (l[v] || !rn[u][v]) continue;
            l[v] = l[u] + 1;
            q.push(v);
        }
    }

    return l[T];
}

int dinicDFS(int u, int cp)
{
    if (u == T) return cp;

    int tmp = cp;

    FOR(v, 0, T + 1 && tmp)
    {
        if (l[v] != l[u] + 1 || !rn[u][v]) continue;
        int bt = dinicDFS(v, min(rn[u][v], tmp));
        rn[u][v] -= bt;
        rn[v][u] += bt;
        tmp -= bt;
    }

    return cp - tmp;
}

int maximumFlow()
{
    int mf = 0;
    while (dinicBFS()) mf += dinicDFS(S, INF);
    return mf;
}

void solve()
{
    cout << maximumFlow() << '\n';
}

int main()
{
    while (cin >> Y >> X >> P)
    {
        init();
        read();
        solve();
    }
}

參考資料

UVA 11380 - Down Went The Titanic（网络流）_Remilia’s-CSDN博客