[大意]：有m个猪圈每个中有一定数目的猪但无容量上限，n个顾客么个顾客需要一定数目的猪。每个顾客可以打开特定的猪圈从中取猪，此时这几个猪圈里的猪可以互相流动。问最多可以卖出多少头猪。
[关键字]：网络流
//=====================================================================================================
[分析]：最原始的想法，可以把每个猪圈看成一个点每个顾客看成一个点，然后猪圈的初始数目就是超级源到猪圈点的边容量，每个顾客需要的猪的数量就是顾客点到超级汇的边的容量，一旦猪圈和顾客有联系就把这个猪圈和顾客间连一条∞的边，并把这个顾客所能打开的猪圈之间连一条∞的边，然后对此图求最大流就是最终结果。这样倒是能得到争取答案但时间和空间都不允许，所以要改变思路。因为每个猪圈点所起的作用只是卡初始猪数这个条件所以可以把猪圈点省去，只见在超级源和顾客点之间连容量为初始猪数的边，而顾客和超级汇之间的边不用变。同时如果有同样也能打开同一个猪圈的顾客，那他一定是在他之前的能打开此猪圈的顾客使用后，才能用不与他相联却与其它能打开此猪圈的顾客相连的猪圈里的猪，所以要把这样的顾客和上一个能打开这个猪圈的顾客连一条∞的边，这个顾客的其它能打开的猪圈也同样处理，然后对此图求最大流即可。
[代码]：
View Code #include#include using namespace std; static int n,m,s,t; static int c[500][500],f[500][500],g[2000][2]; static int d[500],l[500]; void init() { scanf("%d %d",&m,&n); memset(c,0,sizeof(c)); memset(f,0,sizeof(f)); s=0; t=n+1; int tot,ph; for (int i=1;i<=m;i++) { g[i][0]=s; scanf("%d",&g[i][1]); } for (int i=1;i<=n;i++) { scanf("%d",&tot); for (int j=1;j<=tot;j++) { scanf("%d",&ph); if (g[ph][0]==s) c[s][i]+=g[ph][1]; else c[g[ph][0]][i]=INT_MAX; g[ph][0]=i; } scanf("%d",&tot); c[i][t]=tot; } /* while (1) { scanf("%d %d",&tot,&ph); printf("%d",c[tot][ph]); }*/ } bool bfs() { queue q; memset(l,0,sizeof(l)); q.push(s); l[s]=1; while (!q.empty()) { int u=q.front(); q.pop(); for (int i=s;i<=t;i++) if (!l[i]&&c[u][i]>f[u][i]) { q.push(i); l[i]=l[u]+1; } } return l[t]!=0; } int dfs(int u,int cp) { int temp=cp; if (u==t) return cp; for (int i=s;i<=t&&temp;i++) { if (l[i]==l[u]+1&&c[u][i]>f[u][i]) { int t=dfs(i,min(temp,c[u][i]-f[u][i])); f[u][i]+=t; f[i][u]-=t; temp-=t; } } return cp-temp; } int dinic() { int tf=0,ans=0; while (bfs()) { while (tf=dfs(s,INT_MAX)) ans+=tf; } return ans; } int main() { init(); printf("%d\n",dinic()); //system("pause"); return 0; }
