本文主要是介绍POJ 3281 Dining 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题意】：
有F种食物和D种饮料，每种食物或饮料只能供一头牛享用，且每头牛只享用一种食物和一种饮料。现在有n头牛，每头牛都有自己喜欢的食物种类列表和饮料种类列表，问最多能使几头牛同时享用到自己喜欢的食物和饮料。
【分析】：
这是一道匹配问题，我们可以用网络流建模来解决。
先考虑建立食物—牛—饮料的图，即：
1）：源点S向每种食物连容量为1的有向边
2）：每种食物向对应的牛（喜欢吃该食物的牛）连容量为1的有向边
3）：每头牛向喜欢喝的饮料连容量为1的有向边
4）：每种饮料向汇点T连容量为1的有向边
这种建模方式，思考一下，每种食物或饮料的确是只能供一头牛享用，因为受到了S到食物和饮料到T的容量1的限制，使得每个饮料和食物都只被用一次，但是，仔细想来，并未满足每头牛只享用一种食物和一种饮料。因为某头牛可能喜欢吃多种食物和饮料，而那头牛之前可能之前已匹配过一种食物和一种饮料，但可能存在之后的某次增广过程，是从那头牛喜欢吃的另一种食物进入牛这个点，且能从另一种饮料到达T，从而完成一次增广。
因而，我们还需加一类边：
5）：将每头牛拆成入点和出点，入点到出点连一条容量为1的有向边
这样，就能满足“每种食物或饮料只能供一头牛享用，且每头牛只享用一种食物和一种饮料”这两个条件了。
【代码】：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXNODE 402
#define MAXE 4610
#define IMAX 214748364
struct EDGE{int f,t,next,flow;}a[MAXE];
int N,F,D,tot=0,last[MAXNODE],ans=0,S,T;
int d[MAXNODE],Q[MAXE];
bool map[MAXNODE][MAXNODE];
void add(int from,int to,int flow)
{a[tot].t=to;a[tot].flow=flow;a[tot].next=last[from];last[from]=tot++;a[tot].t=from;a[tot].flow=0;a[tot].next=last[to];last[to]=tot++;
}
bool build()
{int right=0;for(int i=S;i<=T;i++)d[i]=IMAX;d[S]=0;Q[++right]=S;for(int left=1;left<=right;left++){int now=Q[left];for(int i=last[now];i!=-1;i=a[i].next){int to=a[i].t;if(a[i].flow && d[now]+1<d[to]){d[to]=d[now]+1;if(to==T) return true;Q[++right]=to;}}}return false;
}
int DINIC(int now,int flow)
{if(!flow) return 0;if(now==T) return flow;int rem=flow,use;for(int i=last[now];i!=-1;i=a[i].next){int to=a[i].t;if(d[to]==d[now]+1 && (use=DINIC(to,min(flow,a[i].flow)))){a[i].flow-=use;a[i^1].flow+=use;flow-=use;}}if(rem==flow) d[now]=-1;return rem-flow;
}
void MaxFlow()
{int use;while(build()){while(use=DINIC(S,IMAX))ans+=use;}
}
int main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);memset(last,-1,sizeof(last));scanf("%d%d%d",&N,&F,&D);S=0;T=F+2*N+D+1;for(int i=1;i<=F;i++)add(S,i,1); for(int i=1;i<=N;i++)add(F+i,F+N+i,1);for(int i=1;i<=D;i++)add(F+2*N+i,T,1);for(int i=1;i<=N;i++){int f,d;scanf("%d%d",&f,&d);for(int j=1;j<=f;j++){int foodnum;scanf("%d",&foodnum);if(!map[foodnum][F+i]){add(foodnum,F+i,1);map[foodnum][F+i]=true;}}for(int j=1;j<=d;j++){int drinknum;scanf("%d",&drinknum);if(!map[F+N+i][F+2*N+drinknum]){add(F+N+i,F+2*N+drinknum,1);map[F+N+i][F+2*N+drinknum]=true;}}}MaxFlow();printf("%d\n",ans);return 0;
}这篇关于POJ 3281 Dining 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
