PAT顶级1003 - 最大网络流_pintia.cn

// PAT top 1003
// https://pintia.cn/problem-sets/994805148990160896/problems/994805155688464384

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

using cap_type = int;

const cap_type INF = 1 << 28;
const int MAX_N = 1024;

struct Edge
{
    int to;
    int next;
    cap_type cap;
    Edge(int to = 0, int next = 0, cap_type cap = 0) : to(to), next(next), cap(cap) {}
} G[2 * MAX_N];
int head[MAX_N], deg;
bool used[MAX_N];
void init(int n);
void add_edge(int u, int v, cap_type cap);
cap_type dfs(int T, int n, cap_type f);
cap_type max_flow(int S, int T);

int main()
{
    string u, v;
    int N, M = 3;

    cin >> u >> v >> N;

    init(N);
    unordered_map<string, int> dir{{u, 1}, {v, 2}};
    for (cap_type cap; N--;)
    {
        cin >> u >> v >> cap;
        int &_u = dir[u], &_v = dir[v];
        if (!_u)
            _u = M++;
        if (!_v)
            _v = M++;
        add_edge(_u, _v, cap);
    }
    cout << max_flow(1, 2);
    return 0;
}

void init(int n)
{
    fill(head, head + n + 8, -1);
    deg = 0;
}

void add_edge(int u, int v, cap_type cap)
{
    G[deg] = Edge(v, head[u], cap);
    head[u] = deg++;
    G[deg] = Edge(u, head[v], 0);
    head[v] = deg++;
}

cap_type dfs(int T, int n, cap_type f)
{
    used[n] = true;
    if (n == T)
    {
        return f;
    }
    for (int i = head[n]; ~i; i = G[i].next)
    {
        auto &e = G[i];
        if (!used[e.to] && e.cap)
        {
            cap_type d = dfs(T, e.to, min(e.cap, f));
            if (d)
            {
                e.cap -= d;
                G[i ^ 1].cap += d;
                return d;
            }
        }
    }
    return 0;
}

cap_type max_flow(int S, int T)
{
    cap_type flow = 0, f;
    do
    {
        fill(used, used + MAX_N, false);
        f = dfs(T, S, INF);
        flow += f;
    } while (f);
    return flow;
}
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