Solution P4638
广告
我的博客
双倍经验
SP4063 MPIGS - Sell Pigs
没有 SPOJ 的账号的同学， 不建议食用。
这个题数据范围要大一些， 所以直接交过去就可以过了。
前置知识
P3376 【模板】网络最大流
这里附赠一个模板。
食用方法： 对于每道题， 先将模板复制下来， 然后调整点数 N 的大小和边数 M 的大小， 建图即可。 注意 st 虚拟源点默认为最小的点， ed 虚拟汇点默认为最大的点， 注意将 hd 数组赋初始值 -1。
#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#define inf INT_MAX
using namespace std;
const int N = + 10, M = + 10;
int n, st, ed, d[N], cur[N];
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])
{
cur[edg[i]] = hd[edg[i]];
d[edg[i]] = d[t] + 1;
if (edg[i] == ed)
return true;
q.push(edg[i]);
}
}
return false;
}
int exploit(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 = exploit(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 = exploit(st, inf))
res += flow;
return res;
}
void add (int a, int b, int c)
{
nxt[++idx] = hd[a];
hd[a] = idx;
edg[idx] = b;
wt[idx] = c;
}
int main ()
{
return 0;
}正文
题目中， 金币从保险柜里面流出， 到达每个人都手中， 求可以取出的最大值。 这不禁让我们联想到了网络最大流， 保险柜正是虚拟源点， 可以流出流量， 而金币正是流量。 这道题目特殊的一点是每一个人取出金币之后， 可以随意调整打开的保险柜的数量。 那么可能因为这次调整多出来的流量是因为两人用了同一个保险柜， 即可能存在的金币的流向如下：
客户 1 打开了保险柜 1， 2
保险柜 1 -> 客户 1
保险柜 2 -> 客户 1
此时， 保险柜 1 和 2 以及客户 1 之间可以随便乱搞
保险柜 1 -> 保险柜 2 （被 “ 你 ” 拿走）
客户 2 打开了保险柜 2
此时， 保险柜 2 和客户 2 之间可以随便乱搞
保险柜 2 -> 客户 2
不难发现， 保险柜 1 和 2 与客户 1 和 2 之间金币可以按顺序随意流动， 所以上述过程可以等价于
客户 1 打开了保险柜 1， 2
客户 1 十分贪婪， 卷走所有的保险柜 1 和 2 的金币
客户 2 一来， 看见自己的保险柜 2 被卷走了， 十分生气， 把客户 1 打了一顿， 拿走了他想要的金币于是我们可以这样建图：
-
建立虚拟源点和汇点；
-
对于每一个人能开的保险柜， 如果它没有被打开过， 则从虚拟源点到当前的人连一条流量为保险柜金币数量的边， 表示这个人可以从这个保险柜中卷走所有的金币；
-
对于每一个人能开的保险柜， 如果它已经被打开过了， 则从上一次可以开这个保险柜的人到当前的人连一条流量为无限大的边， 表示当前的人可以无限从上一个人索取金币；
-
对于每个人， 向汇点连一条流量为其想要的金币的数量。
可以发现， 对于一个保险柜， 所有可以打开它的人构成了一条链， 可以按顺序随意传播金币。
代码
#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;
}难度评定
该题目难度还暂无评定， 建议设置其难度为 省选/NOI- 。