原题链接
有 m 个猪圈，开始时第 i 个猪圈有 ai 头猪，每个猪圈都是锁门的，要是不相同。管理员没有猪圈的钥匙。依次来了 m 个顾客，第 i 个顾客有 Ai 把猪圈钥匙（哪几个都告诉你）话说为什么钥匙会在顾客手中啊 ，需要至多Bi 头猪。每个顾客打开这几个猪圈，然后管理员可以把打开门的几个猪圈里的猪进行调整（比如把 A 猪圈的其中一头猪带到 B 猪圈）。要求的是管理员最多能卖出多少猪。
n≤100,m≤1000。
题解
一道有趣的网络流建模题……
首先当然要建超源（S）和超汇（T）。
把每个顾客都看成一个点。
每个顾客向 T 连一条容量为 Bi 的边，表示每个顾客最多买 Bi 头猪。
首先是 S 向每个猪圈第一个打开门的顾客连边，边权为ai，即猪圈内猪的数量，表示猪圈一开始能供应给顾客的猪。
如果某个顾客打开了猪圈 X（即有猪圈X 的钥匙），那么他所能“看”到的猪（即如果 Bi=∞ 时他所能买到的猪）下一个打开 X 的顾客也能买到，所以每个顾客都像下一个打开这些门的顾客连边，边权为 $\infty$。
建图代码如下：
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
| inline int solve()
{
memset(first, 0xff, sizeof(first));
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; ++i)
scanf("%d", &yuan[i]);
for(int i = 1; i <= n; ++i)
{
int tn;
scanf("%d", &tn);
for(int j = 1, x; j <= tn; ++j)
{
scanf("%d", &x);
mmap[lst[x]][i] = lst[x] ? inf : mmap[lst[x]][i] + yuan[x];
lst[x] = i;
}
scanf("%d", &tn);
add_edge(i, n + 1, tn);
}
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= n; ++j)
if(mmap[i][j])
add_edge(i, j, mmap[i][j]);
for(register int i = 0; i <= n + 1; ++i)
first_bak[i] = first[i];
return Dinic();
}
|
