题意： 有 M 个猪圈，每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依次来了 N 个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪。每个顾客分别都有他能够买的数量的上限。每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。
构图：
(1) 将顾客看作源点和汇点以外的结点，并设一个源点和汇点
(2)源点和每个猪圈的第一个顾客连边，边权是开始时猪圈中猪的数目
(3)顾客j在顾客i之后打开猪圈，i，j 之间连一条权值为inf的边，因为迈克可以根据j的需要，从其他猪圈调猪过来，让j得到尽可能多的猪
(4)每个顾客和汇点连一条权值为顾客要买猪的数目 的边
(5)然后就是套模板了。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 using namespace std; 7 #define inf 0x7fffffff 8 #define N 105 9 #define M 10005 10 int size,head[N]; 11 int cur[N],pre[N],dis[N],gap[N]; 12 int last[1005],house[1005]; 13 struct Edge 14 { 15 int v,w,next; 16 Edge(){} 17 Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){} 18 }edge[M]; 19 void Init() //初始化 20 { 21 memset(head,-1,sizeof(head)); 22 memset(last,-1,sizeof(last)); 23 size = 0; 24 } 25 void InsertEdge(int u,int v,int w) //加边 26 { 27 edge[size] = Edge(v,w,head[u]); 28 head[u] = size++; 29 edge[size] = Edge(u,0,head[v]); 30 head[v] = size++; 31 } 32 33 int Isap(int st,int ed,int n)//n为结点个数，Isap模板 34 { 35 for(int i=0; i<=n; i++) 36 { 37 dis[i] = gap[i] = 0; 38 cur[i] = head[i]; 39 } 40 int u = pre[st] = st; 41 int aug = inf , maxflow = 0; 42 while(dis[st] < n) 43 { 44 loop: 45 for(int &i=cur[u]; i!=-1; i = edge[i].next) 46 { 47 int v = edge[i].v; 48 if(edge[i].w && dis[u] == dis[v]+1) 49 { 50 aug = aug < edge[i].w ? aug:edge[i].w; 51 pre[v] = u; 52 u = v; 53 if(v == ed) 54 { 55 maxflow += aug; 56 for( u = pre[u]; v!=st; v = u,u = pre[u]) 57 { 58 edge[cur[u]].w -= aug; 59 edge[cur[u]^1].w += aug; 60 } 61 aug = inf; 62 } 63 goto loop; 64 } 65 } 66 int mindis = n; 67 for(int i = head[u]; i!=-1; i=edge[i].next) 68 { 69 int v = edge[i].v; 70 if(edge[i].w && dis[v] < mindis) 71 { 72 cur[u] = i; 73 mindis = dis[v]; 74 } 75 } 76 if(--gap[dis[u]]==0) break; 77 gap[dis[u] = mindis+1]++; 78 u = pre[u]; 79 } 80 return maxflow; 81 } 82 83 int main() 84 { 85 int m,n,num,k,st,ed,nv; 86 scanf("%d%d",&m,&n); 87 Init(); 88 st = 0; // 附加源点 89 ed = n+1; //附加汇点 90 nv = n+2; //结点个数 91 for(int i=1; i<=m; i++) 92 scanf("%d",&house[i]); 93 for(int i=1; i<=n; i++) 94 { 95 scanf("%d",&num); 96 for(int j=0; j<num; j++) 97 { 98 scanf("%d",&k); 99 if(last[k]!=-1) //last数组记录k是不是第一次打开 100 InsertEdge(last[k],i,inf); //(3) 101 else 102 { 103 InsertEdge(st,i,house[k]); //(2) 104 last[k] = i; 105 } 106 } 107 scanf("%d",&k); 108 InsertEdge(i,ed,k); //(4) 109 } 110 int ans = Isap(st,ed,nv); 111 printf("%d ",ans); 112 return 0; 113 }