题目链接
题意
(n)个顾客要买猪，每个人希望买若干头猪；一共有(m)个猪圈，每个猪圈里有若干头猪。
第(i)个顾客有(k_i)把钥匙，可以打开一些指定的猪圈门，并且买这些猪圈里的猪；在他离开之前，这些猪圈里的猪可以随意交换位置，然后猪圈门被关上。
问最多可以卖出去多少头猪？
建图方式
首先要加的一些边是很显然的：
-
源点(slongrightarrow)每个顾客，边权为顾客希望买的猪的个数；
-
每个猪圈(longrightarrow)汇点(t)，边权为这个猪圈里猪的个数；
-
每个顾客到他可以打开的猪圈门连条边，边权为(inf)。
再来考虑题中的特殊条件，每一次打开的所有猪圈的猪可以任意交换位置，这意味着什么呢？
考虑：
第(i)个顾客打开第(y)扇猪圈门，在他打开第(y)扇门的时候，里面除了会有第(y)扇门原来里面的猪，还会有之前经过交换而来的猪，而交换的来源，就是在此之前打开过第(y)扇门的所有顾客，他们打开的其他门。
这就意味着当前打开第(y)扇门的顾客，他拥有之前所有打开过第(y)扇门的顾客的选择。
于是，可以 在当前打开第(y)扇门的顾客 到 之前所有打开过第(y)扇门的顾客 之间连条边权为(inf)的边。
进一步的，因为这个关系具有传递性，所有只需在 当前打开第(y)扇门的顾客 和 上一位打开第(y)扇门的顾客 之间连边即可。
Code
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#define maxm 200010
#define maxn 1010
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
int n, m, x;
struct Edge { int to, ne, c; }edge[maxm];
int dep[maxn], ne[maxn], f,d, tot, s,t, vis[maxn];
void add(int u, int v, int c) {
edge[tot] = {v, ne[u], c};
ne[u] = tot++;
edge[tot] = {u, ne[v], 0};
ne[v] = tot++;
}
int bfs(int src) {
memset(dep, 0, sizeof dep);
dep[src] = 1;
queue<int> q;
while (!q.empty()) q.pop();
q.push(src);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = ne[u]; ~i; i = edge[i].ne) {
int v = edge[i].to;
if (edge[i].c > 0 && !dep[v]) dep[v] = dep[u] + 1, q.push(v);
}
}
return dep[t];
}
int dfs(int u, int flow) {
if (u == t) return flow;
int ret = 0;
for (int i = ne[u]; ~i; i = edge[i].ne) {
int v = edge[i].to;
if (edge[i].c > 0 && dep[v] == dep[u] + 1) {
int c = dfs(v, min(flow-ret, edge[i].c));
edge[i].c -= c;
edge[i^1].c += c;
ret += c;
if (ret == flow) break;
}
}
if (!flow) dep[u] = 0;
return ret;
}
int main() {
scanf("%d%d", &m, &n);
s = 0, t = n+m+1, tot = 0, memset(ne, -1, sizeof(ne));
memset(vis, -1, sizeof(vis));
for (int i = 1; i <= m; ++i) {
scanf("%d", &x);
add(n+i, t, x);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
while (x--) {
int y;
scanf("%d", &y);
if (~vis[y]) add(i, vis[y], inf);
vis[y] = i;
add(i, n+y, inf);
}
scanf("%d", &x);
add(s, i, x);
}
int ans=0, ret;
while (bfs(s)) {
while (ret = dfs(s, inf)) ans += ret;
}
printf("%d
", ans);
return 0;
}