洛谷P1343地震逃生_EK

发表于 更新于 分类于 本文字数： 254 阅读时长 ≈ 1 分钟

用EK算法来做最大流问题，相较于FF算法，EK算法先用bfs找出最小流，然后从汇点开始扣减容量到汇点

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

const int N = 2e3 + 86;
struct edge
{
    int to, nxt, w;
} e[N * 2];
int hd[N], tot = 1;
void add(int u, int v, int w)
{
    e[++tot] = (edge){v, hd[u], w};
    hd[u] = tot;
}
int n, m, x, flow[N], last[N];
bitset<286> vis;

int bfs()
{
    memset(last, 0, sizeof(last));
    queue<int> q;
    q.push(1);
    flow[1] = 9e8 + 86;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        if (p == n)
            break;
        for (int eg = hd[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            if (vol > 0 && !last[to])
            {
                last[to] = eg;
                flow[to] = min(flow[p], vol);
                q.push(to);
            }
        }
    }
    return last[n];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //IN;OUT;
    cin >> n >> m >> x;
    f(i, 1, m)
    {
        int x, y, val;
        cin >> x >> y >> val;
        add(x, y, val);
        add(y, x, 0);
    }
    LL ans = 0;
    while (bfs())
    {
        ans += flow[n];
        for (int i = n; i != 1; i = e[last[i] ^ 1].to) // 从汇点原路返回更新残余容量
        {
            e[last[i]].w -= flow[n];
            e[last[i] ^ 1].w += flow[n];
        }
    }
    if (ans)
    {
        cout << ans << " ";
        cout << (x / ans + (x % ans ? 1 : 0));
    }
    else
        cout << "Orz Ni Jinan Saint Cow!";
    return 0;
}