首页 > 代码库 > HDU4292_Food

HDU4292_Food

2024-07-11 20:04:53   222人阅读

给出一些人，一些食物，一些饮料，每个人都只喜欢喝某些饮料，吃某些食品，每个食品和饮料都有一定的数量，现在问最多能满足多少人的需求。

注意理解题意了，每个人只需要要拿一个食物和一个饮料即可，这题目说得好像不是很明显，坑呐。

简单建模。超级源点->食物->人->人‘->饮料->超级汇点。除了与源点和汇点的边容量为食物和饮料数量，其他的都为1.

跑最大流，就是答案了。。不多说

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 1010#define maxm 2000100using namespace std;int first[maxn],next[maxm],to[maxm],c[maxm],N;int d[maxn],tag[maxn],TAG=520;int s,t,n,F,D,ans,tmp;char str[maxn][maxn];int Q[maxn],bot,top;bool can[maxn];void _init(){	s=0,t=F+D+n+n+1,N=-1;	for (int i=s; i<=t; i++) first[i]=-1;}void addedge(int U,int V,int W){	N++;	to[N]=V,c[N]=W,next[N]=first[U],first[U]=N;	N++;	to[N]=U,c[N]=0,next[N]=first[V],first[V]=N;}void edge_build(){	for (int i=1; i<=F; i++) scanf("%d",&tmp),addedge(s,i,tmp);	for (int i=1; i<=D; i++) scanf("%d",&tmp),addedge(F+n+n+i,t,tmp);	for (int i=1; i<=n; i++) scanf("%s",str[i]+1);	for (int i=1; i<=n; i++)		for (int j=1; j<=F; j++)			if (str[i][j]==‘Y‘) addedge(j,F+i,1);	for (int i=1; i<=n; i++) scanf("%s",str[i]+1);	for (int i=1; i<=n; i++)		for (int j=1; j<=D; j++)			if (str[i][j]==‘Y‘) addedge(F+n+i,F+n+n+j,1);	for (int i=1; i<=n; i++) addedge(F+i,F+n+i,1);}bool bfs(){	TAG++;	Q[bot=top=1]=t,d[t]=0,tag[t]=TAG,can[t]=false;	while (bot<=top)	{		int cur=Q[bot++];		for (int i=first[cur]; i!=-1; i=next[i])			if (c[i^1]>0 && tag[to[i]]!=TAG)			{				tag[to[i]]=TAG,Q[++top]=to[i],d[to[i]]=d[cur]+1,can[to[i]]=false;				if (to[i]==s) return true;			}	}	return false;}int dfs(int cur,int num){	if (cur==t) return num;	int tmp=num,k;	for (int i=first[cur]; i!=-1; i=next[i])		if (c[i]>0 && tag[to[i]]==TAG && d[to[i]]==d[cur]-1 && can[to[i]]==false)		{			k=dfs(to[i],min(num,c[i]));			if (k) num-=k,c[i]-=k,c[i^1]+=k;			if (num==0) break;		}	if (num) can[cur]=true;	return tmp-num;}int main(){	while (scanf("%d%d%d",&n,&F,&D)!=EOF)	{		_init();		edge_build();		for (ans=0; bfs(); bfs()) ans+=dfs(s,maxm);		printf("%d\n",ans);	}	return 0;}

　　


联系
我们