题意：
m n //有m个猪圈，n个人卖猪。
a1...am //编号为i的猪圈里有ai头猪。
b1 c1...cb1 d1 //第i个人有bi把钥匙，分别是ci猪圈的，其它猪圈里的猪都是锁着的 他最多买di头猪
.
.
.
bn c1...cbn dn
注意的是假如某买主有第一和第二个猪圈的钥匙，那么他买完猪以后这两个猪圈的个数我们可以随意调整，调整完将猪圈锁上。
求：最多能卖多少猪
思路：
源点到每个猪圈建边，容量为这个猪圈的猪的数量，然后买主与他有钥匙的猪圈建边，容量inf。买主与其它与以前与他在同一个猪圈买过猪的买主建边，容量是inf，然后每个买主与汇点建边，容量是他最多买的猪的数目。跑一下最大流。
#include<stdio.h> #include<string.h> #include<algorithm> #include<string.h> #include<vector> #define MAXN 1500 #define MAXM 50000 using namespace std; const int inf=0x3f3f3f3f; vector<int> jilu[1010]; struct Edge { int v,c,f,nx; Edge() {} Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {} } E[MAXM]; int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],sz; void init() { sz=0; memset(G,-1,sizeof(G)); } void add_edge(int u,int v,int c) { E[sz]=Edge(v,c,0,G[u]); G[u]=sz++; E[sz]=Edge(u,0,0,G[v]); G[v]=sz++; } bool bfs(int S,int T) { static int Q[MAXN]; memset(dis,-1,sizeof(dis)); dis[S]=0; Q[0]=S; for (int h=0,t=1,u,v,it;h<t;++h) { for (u=Q[h],it=G[u];~it;it=E[it].nx) { if (dis[v=E[it].v]==-1&&E[it].c>E[it].f) { dis[v]=dis[u]+1; Q[t++]=v; } } } return dis[T]!=-1; } int dfs(int u,int T,int low) { if (u==T) return low; int ret=0,tmp,v; for (int &it=cur[u];~it&&ret<low;it=E[it].nx) { if (dis[v=E[it].v]==dis[u]+1&&E[it].c>E[it].f) { if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f))) { ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp; } } } if (!ret) dis[u]=-1; return ret; } int dinic(int S,int T) { int maxflow=0,tmp; while (bfs(S,T)) { memcpy(cur,G,sizeof(G)); while (tmp=dfs(S,T,inf)) maxflow+=tmp; } return maxflow; } int main() { init(); int m,n; scanf("%d%d",&m,&n); int s=0,t=n+m+1; for(int i=1;i<=m;i++){ int tmp; scanf("%d",&tmp); add_edge(s,i,tmp); } for(int i=1;i<=n;i++){ int nn; scanf("%d",&nn); for(int j=0;j<nn;j++){ int tmp; scanf("%d",&tmp); add_edge(tmp,i+m,inf); for(int k=0;k<jilu[tmp].size();k++){ add_edge(jilu[tmp][k],i+m,inf); } jilu[tmp].push_back(i+m); } scanf("%d",&nn); add_edge(i+m,t,nn); } printf("%d ",dinic(s,t)); }