http://poj.org/problem?id=1149
有 M 个猪圈，每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依 次来了 N 个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪。每 个顾客分别都有他能够买的数量的上限。每个顾客走后，他打开的那些猪圈中的 猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。问总共 最多能卖出多少头猪。（1 <= N <= 100, 1 <= M <= 1000）
举个例子来说。有 3 个猪圈，初始时分别有 3、 1 和 10 头猪。依次来了 3 个顾客， 第一个打开 1 号和 2 号猪圈，最多买 2 头；第二个打开 1 号和 3 号猪圈，最多买 3 头；第三个打开 2 号猪圈，最多买 6 头。那么，最好的可能性之一就是第一个 顾客从 1 号圈买 2 头，然后把 1 号圈剩下的 1 头放到 2 号圈；第二个顾客从 3 号圈买 3 头；第三个顾客从 2 号圈买 2 头。总共卖出 2+3+2=7 头。
让我们从图 4 中重新总结一下构造这个网络模型的规则： • 每个顾客分别用一个结点来表示。 • 对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的 猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一 条，容量相加。 • 对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i∈[1, n)，从该 猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为∞。 • 从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。
因为顾客有顺序，所以最开始想的建图是多来几个猪圈，几个顾客就拆多少个点，但是很难实现，于是画个图，可以缩点！以人为节点建图，确实很巧妙
#include <cstdio> #include <iostream> #include <cstring> #include <queue> using namespace std; const int INF = (1<<30); int pig[1100],flag[1100],res[110][110],dis[110]; int m,n; //m猪圈，n个人 int S = 0,T ; void init(){ for(int i = 1 ; i <= m ;i++) scanf("%d",&pig[i]); memset(res,0,sizeof(res)); memset(flag,0,sizeof(flag)); for(int i = 1 ; i <= n ;i++){ int num; scanf("%d",&num); for(int j = 0 ; j < num ;j++){ int room; scanf("%d",&room); if(flag[room] == 0) res[S][i] += pig[room]; else res[flag[room]][i] = INF; flag[room] = i; } int xu; scanf("%d",&xu); res[i][T] = xu; } } int bfs(){ int tmp; queue<int>q; memset(dis,-1,sizeof(dis)); dis[T] = 0; q.push(T); while(!q.empty()){ tmp = q.front(); if(tmp == S) return 1; q.pop(); for(int i = 0 ; i <= T;i++){ if(dis[i] == -1&&res[i][tmp]){ dis[i] = dis[tmp]+1; q.push(i); } } } return 0; } int dfs(int cur,int c){ if(cur == T) return c; int tmp = c,flow; for(int i = 0 ; i <= T ;i++){ if(tmp == 0) break; if(dis[i]+1 == dis[cur]&&res[cur][i]){ flow = dfs(i,min(res[cur][i],tmp)); res[cur][i] -= flow; res[i][cur] += flow; tmp -= flow; } } return c-tmp; } void dinic(){ int maxflow = 0; while(bfs()) maxflow += dfs(S,INF); printf("%d\n",maxflow); } int main(){ while(~scanf("%d%d",&m,&n)){ T = n+1; init(); dinic(); } }