Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P4638 [SHOI2011]银行家

发表于 分类于
本文字数： 3.3k 阅读时长 ≈ 3 分钟
标签：    

P4638 [SHOI2011]银行家

以下是当时写的题解。

题目中， 金币从保险柜里面流出， 到达每个人都手中， 求可以取出的最大值。 这不禁让我们联想到了网络最大流， 保险柜正是虚拟源点， 可以流出流量， 而金币正是流量。 这道题目特殊的一点是每一个人取出金币之后， 可以随意调整打开的保险柜的数量。 那么可能因为这次调整多出来的流量是因为两人用了同一个保险柜， 即可能存在的金币的流向如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
客户 1 打开了保险柜 1， 2

保险柜 1 -> 客户 1

保险柜 2 -> 客户 1

此时， 保险柜 1 和 2 以及客户 1 之间可以随便乱搞

保险柜 1 -> 保险柜 2 （被 “ 你 ” 拿走）

客户 2 打开了保险柜 2

此时， 保险柜 2 和客户 2 之间可以随便乱搞

保险柜 2 -> 客户 2

不难发现， 保险柜 1 和 2 与客户 1 和 2 之间金币可以按顺序随意流动， 所以上述过程可以等价于

1
2
3
4
5
客户 1 打开了保险柜 1， 2

客户 1 十分贪婪， 卷走所有的保险柜 1 和 2 的金币

客户 2 一来， 看见自己的保险柜 2 被卷走了， 十分生气， 把客户 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
#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#define INF INT_MAX
using namespace std;
const int N = 610, M = 4e6 + 10;
int m, n, st, ed, k[2510], d[N], cur[N], last[2510];
int idx = -1, hd[N], nxt[M], edg[M], wt[M];
bool bfs ()
{
    for (int i = st; i <= ed; i++)
        d[i] = -1;
    d[st] = 0;
    cur[st] = hd[st];
    queue <int> q;
    q.push(st);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = hd[t]; ~i; i = nxt[i])
            if (d[edg[i]] == -1 && wt[i])
            {
                d[edg[i]] = d[t] + 1;
                cur[edg[i]] = hd[edg[i]];
                if (edg[i] == ed)
                    return true;
                q.push(edg[i]);
            }
    }
    return false;
}
int find (int x, int limit)
{
    if (x == ed)
        return limit;
    int res = 0;
    for (int i = cur[x]; ~i && res < limit; i = nxt[i])
    {
        cur[x] = i;
        if (d[edg[i]] == d[x] + 1 && wt[i])
        {
            int t = find(edg[i], min(wt[i], limit - res));
            if (!t)
                d[edg[i]] = -1;
            wt[i] -= t;
            wt[i ^ 1] += t;
            res += t;
        }
    }
    return res;
}
int dinic ()
{
    int res = 0, flow;
    while (bfs())
        while (flow = find(st, INF))
            res += flow;
    return res;
}
void add (int x, int y, int z)
{
    nxt[++idx] = hd[x];
    hd[x] = idx;
    edg[idx] = y;
    wt[idx] = z;
}
int main ()
{
    cin >> m >> n;
    st = 0;
    ed = n + 1;
    for (int i = st; i <= ed; i++)
        hd[i] = -1;
    for (int i = 1; i <= m; i++)
        cin >> k[i];
    for (int i = 1, a, b, id; i <= n; i++)
    {
        cin >> a;
        while (a--)
        {
            cin >> id;
            if (!last[id])
            {
                add(st, i, k[id]);
                add(i, st, 0);
            }
            else
            {
                add(last[id], i, INF);
                add(i, last[id], 0);
            }
            last[id] = i;
        }
        cin >> b;
        add(i, ed, b);
        add(ed, i, 0);
    }
    cout << dinic();
    return 0;
}
相关文章