主要是构图。
刚开始我想的是源点->牛->食物->饮料，发现问题很多，正确的构图应该是源点->食物->牛->牛->饮料->汇点，中间牛与牛之间的容量为1。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=1005; const int INF=999999999; int n,m,F,D; int f[maxn][maxn]; int pre[maxn]; int vis[maxn]; void Max_Flow() { int t,i,temp,sum=0; while(1) { queue q; memset(vis,0,sizeof(vis)); memset(pre,0,sizeof(pre)); vis[0]=1; q.push(0); while(!q.empty()) { t=q.front(); q.pop(); if(t==n+n+D+F+1) break; for(i=0;i<=n+n+F+D+1;i++) { if(!vis[i] && f[t][i]>0) { vis[i]=1; q.push(i); pre[i]=t; } } } if(!vis[n+n+D+F+1]) break; temp=INF; for(i=n+n+F+D+1;i!=0;i=pre[i]) { if(temp>f[pre[i]][i]) temp=f[pre[i]][i]; } for(i=n+n+F+D+1;i!=0;i=pre[i]) { f[pre[i]][i]-=temp; f[i][pre[i]]+=temp; } sum+=temp; } printf("%d\n",sum); } int main() { while(scanf("%d%d%d",&n,&F,&D)!=EOF) { memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { int a,b,p; scanf("%d%d",&a,&b); for(int j=1;j<=a;j++) { scanf("%d",&p); f[0][p]=1; //源点->食物 f[p][F+i]=1; //食物->牛 } f[F+i][F+n+i]=1; //牛->牛 for(int j=1;j<=b;j++) { scanf("%d",&p); f[F+n+i][F+n+n+p]=1; //牛->饮料 f[F+n+n+p][F+n+n+D+1]=1; //饮料->汇点 } } Max_Flow(); } return 0; }