驻马店网站建设维护,如何开发微信小程序开发,厦门营销网站制作,如何做征信公司网站酒店之王 题目描述 XX酒店的老板想成为酒店之王#xff0c;本着这种希望#xff0c;第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等#xff0c;也有自己所爱的菜#xff0c;但是该酒店只有p间房间#xff0c;一天只有固定的q道不同的菜。 有…酒店之王 题目描述 XX酒店的老板想成为酒店之王本着这种希望第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等也有自己所爱的菜但是该酒店只有p间房间一天只有固定的q道不同的菜。 有一天来了n个客人每个客人说出了自己喜欢哪些房间喜欢哪道菜。但是很不幸可能做不到让所有顾客满意满意的条件是住进喜欢的房间吃到喜欢的菜。 这里要怎么分配能使最多顾客满意呢 输入输出格式 输入格式 第一行给出三个正整数表示n,p,q(100)。 之后n行每行p个数包含0或1第i个数表示喜不喜欢第i个房间1表示喜欢0表示不喜欢。 之后n行每行q个数表示喜不喜欢第i道菜。 输出格式 最大的顾客满意数。 输入输出样例 输入样例#12 2 2
1 0
1 0
1 1
1 1输出样例#1 1题解裸的最大流只不过人要拆成两个点用以保证每一个人只用一次。 #includeiostream
#includecstdio
#includecmath
#includealgorithm
#includecstring
#includecstdlib
#includequeue
#includestack
#includevector
#includectime
using namespace std;
int n,m,l;
struct node
{int next,to,cap;
}edge[300001];
int size1,head[501];
void putin(int from,int to,int cap)
{size;edge[size].nexthead[from];edge[size].capcap;edge[size].toto;head[from]size;
}
void in(int from,int to,int cap)
{putin(from,to,cap);putin(to,from,0);
}
int dist[501],numbs[501];
void bfs(int src,int des)
{int i;queueintmem;mem.push(des);numbs[0];while(!mem.empty()){int xmem.front();mem.pop();for(ihead[x];i!-1;iedge[i].next){int yedge[i].to;if(edge[i].cap0dist[y]0y!des){dist[y]dist[x]1;numbs[dist[y]];mem.push(y);}}}return;
}
int dfs(int src,int flow,int des)
{if(srcdes)return flow;int i,low0,mindistnnml2;for(ihead[src];i!-1;iedge[i].next){int yedge[i].to;if(edge[i].cap){if(dist[y]dist[src]-1){int tdfs(y,min(flow-low,edge[i].cap),des);edge[i].cap-t;edge[i^1].capt;lowt;if(dist[src]nnml2)return low;if(lowflow)break;}mindistmin(mindist,dist[y]1);}}if(!low){if(!(--numbs[dist[src]]))dist[nnml2]nnml2;numbs[dist[src]mindist];}return low;
}
int ISAP(int src,int des)
{int ans0;bfs(src,des);while(dist[0]nnml2)ansdfs(src,2e8,des);return ans;
}
int main()
{int i,j;memset(head,-1,sizeof(head));scanf(%d%d%d,n,m,l);for(i1;im;i)in(0,i,1);for(imnn1;imnnl;i)in(i,nnml1,1);for(i1;in;i){for(j1;jm;j){int k;scanf(%d,k);if(k)in(j,mi,1);}}for(i1;in;i){for(j1;jl;j){int k;scanf(%d,k);if(k)in(mni,mnnj,1);}}for(im1;imn;i){in(i,in,1);}printf(%d,ISAP(0,nnml1));return 0;
} 转载于:https://www.cnblogs.com/huangdalaofighting/p/6885888.html
