POJ1149 PIGS（最大流）

题意：

有m个锁着的猪圈，现在有n个顾客过来买猪，他们手里分别有对应猪圈的钥匙，如果已经开了对应的猪圈，就可以在把这个猪圈的猪赶到其他猪圈去，要求能卖出最多的猪数。

要点：

这题建图比较困难，建完图就是个最大流模板。另设一个源和一个汇，将顾客作为其他节点，将猪圈开启的次数作为边，这样先将源点与每个猪圈的第一个顾客连接，如果这个顾客也开了其他猪圈，将猪圈的猪数叠加，这样就构成了一个图，然后接下来的每一个人与前一个打开猪圈的人之间连线.，容量为INF.，因为可以从别的猪圈调猪过来，反正流取最小值，设个无限大保证这条边是通的就行。最后所有顾客与汇点连接，容量是他们要买的猪数量。

#include<iostream>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
#define N 1050
using namespace std;
int n, m;
int a[N], p[N];
int flow[N][N], cap[N][N];void EK(int s, int t)
{memset(p, 0, sizeof(p));memset(flow, 0, sizeof(flow));queue<int> que;int sum = 0;while (1){memset(a, 0, sizeof(a));a[s] = inf;que.push(s);while (!que.empty()){int u = que.front();que.pop();for (int v = 0; v <= n+1; v++){if (!a[v] && flow[u][v] < cap[u][v]){p[v] = u;que.push(v);a[v] = min(a[u], cap[u][v] - flow[u][v]);}}}if (a[t] == 0)break;for (int v = t; v != s; v = p[v]){flow[p[v]][v] += a[t];flow[v][p[v]] -= a[t];}sum += a[t];}cout << sum << endl;
}int main()
{int last[N],pig[N];while (cin >> m >> n){for (int i = 1; i <= m; i++)cin >> pig[i];memset(last, 0, sizeof(last));memset(cap, 0, sizeof(cap));int s = 0, t = n + 1;for (int i = 1; i <= n; i++){int num,temp;cin >> num;while(num--){cin >> temp;if (last[temp] == 0)cap[s][i] += pig[temp];elsecap[last[temp]][i] = inf;last[temp] = i;//last[i]存储上一个开猪圈i的人，说明这两人有重合的猪圈，这样才能转移猪}cin >> cap[i][t];}EK(s, t);}return 0;
}