看论文的时候看到这题了，就做了下。
这题是，如果每头牛可以得到它喜欢的饮料和食物，算一个流量。
开始我想的是把食物和饮料放一起，但是不一定能正确，因为可能是两个饮料流到了牛那里 = =。
论文上说的是，将牛拆分成两个点，这两个点以容量1连接，一个点连饮料，一个点连食物。然后就成了多源点多汇点的最大流。
好神奇~！。。。EK算法297MS。。。看讨论似乎SAP 和 dinic 算法更强。。。学学吧。
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 500 using namespace std; int n,f,d; int cap[MAX][MAX]; int EKarp(int s,int t) { queue<int> Q; int a[MAX],flow[MAX][MAX],pre[MAX]; int f = 0,u,v; memset(flow,0,sizeof(flow)); while(1) { memset(a,0,sizeof(a)); a[s] = INT_MAX; Q.push(s); while( !Q.empty() ) { u = Q.front(); Q.pop(); for(v=s; v<=t; v++) if( !a[v] && cap[u][v] > flow[u][v] ) { Q.push(v); a[v] = a[u] < cap[u][v] - flow[u][v] ? a[u] : cap[u][v] - flow[u][v]; pre[v] = u; } } if( a[t] == 0 ) break; for(u=t; u!=s; u=pre[u]) { flow[pre[u]][u] += a[t]; flow[u][pre[u]] -= a[t]; } f += a[t]; } return f; } int main() { int ff,dd,ans,i; int food,drink; while( scanf("%d%d%d",&n,&f,&d) != EOF ) { memset(cap,0,sizeof(cap)); for(i=1; i<=n; i++) { scanf("%d%d",&ff,&dd); cap[i][i+n] = 1; while( ff-- ) { scanf("%d",&food); cap[2*n+food][i] = 1; } while( dd-- ) { scanf("%d",&drink); cap[i+n][2*n+f+drink] = 1; } } for(i=2*n+1; i<=2*n+f; i++) cap[0][i] = 1; for(i=2*n+f+1; i<=2*n+f+d; i++) cap[i][2*n+f+d+1] = 1; ans = EKarp(0,2*n+f+d+1); printf("%d/n",ans); } return 0; }
