本文主要是介绍poj(3281)Dining,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
难点在于建图;
要将牛拆分成 两个点,一个与drink相连,一个与food相连,这两个点也连,他们的权值为一。。
#include"stdio.h"
#include"string.h"
#include"queue"
#define inf 9999999
int r[900][900];
int pre[900];
int visit[900];
int N,F,D,k;
using namespace std;
int bfs(int s,int t)
{
int p,i;
queue<int>q;
memset(visit,0,sizeof(visit));
memset(pre,0,sizeof(pre));
pre[s]=s;
visit[s]=1;
q.push(s);
while(!q.empty())
{
p=q.front();
q.pop();
for(i=0;i<=k;i++)
{
if(!visit[i]&&r[p][i])
{
visit[i]=1;
pre[i]=p;
if(i==t)
return 1;
q.push(i);
}
}
}
return 0;
}
int EK(int s,int t)
{
int flow=0,d,i;
while(bfs(s,t))
{
d=inf;
for(i=t;i!=s;i=pre[i])
d=d<r[pre[i]][i]?d:r[pre[i]][i];
for(i=t;i!=s;i=pre[i])
{
r[pre[i]][i]-=d;
r[i][pre[i]]+=d;
}
flow+=d;
}
return flow;
}
int main()
{
int n,i,j,fi,di;
while(scanf("%d%d%d",&N,&F,&D)!=EOF)
{
k=N+N+D+F+1;
memset(r,0,sizeof(r));
for(i=1;i<=D;i++)
r[0][i]=1;
for(i=1;i<=F;i++)
r[D+N+N+i][k]=1;
for(i=1;i<=N;i++)
r[D+i][D+N+i]=1;
for(i=1;i<=N;i++)
{
scanf("%d%d",&fi,&di);
for(j=1;j<=fi;j++)
{
scanf("%d",&n);
r[D+N+i][D+N+N+n]=1;
}
for(j=1;j<=di;j++)
{
scanf("%d",&n);
r[n][D+i]=1;
}
}
printf("%d\n",EK(0,k));
}
return 0;
}
这篇关于poj(3281)Dining的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!