luogu1402 酒店之王

luogu1402 酒店之王

(​​ 题目描述 XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有p间房间，一天只有固定的q道不同的菜。 有一天来了n个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间，吃到喜欢的菜）。 这里要怎么分配，能使最多顾客满意呢？ 输入输出格式 输入格式： 第一行给出三个正整数表示n,p,q(<=100)。 之后n行，每行p个数包含0或1，第i个数表示喜不喜欢第i个房间（1表示喜欢，0表示不喜欢）。 之后n行，每行q个数，表示喜不喜欢第i道菜。 输出格式： 最大的顾客满意数。 输入输出样例 输入样例#1： 2 2 2 1 0 1 0 1 1 1 1

输出样例#1： 1 题解：因为每个人只能存在一回 将每个人拆开分成两个点限制流量为1就可以 分为房间 人 菜 三类点连接即可

#include#include#define N 440int r[N][N],d[N][N];int num,h[N],f[N],st[N],S,T,cur[N],n,p,q;struct node{ int x,y,z,next;}data[50000];inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar(); } return x;}inline int min(int a,int b){ return a0&&f[v]==-1){ f[v]=f[u]+1; st[++cl]=v; if (v==T) return true; } } } return false;}int dfs(int u,int s){ if (u==T) return s;int y=h[u],tmp=s; for (int i=cur[u];i!=-1;i=data[i].next){ int v=data[i].y; if (data[i].z>0&&f[v]==f[u]+1){ int x=dfs(v,min(s,data[i].z)); s-=x;y=i;data[i].z-=x;data[i^1].z+=x; if (s==0){ cur[u]=i;return tmp; } } } cur[u]=y; return tmp-s;}int main(){ //freopen("1402.in","r",stdin);// freopen("1402.out","w",stdout); n=read();p=read();q=read(); for (int i=1;i<=n;++i) for (int j=1;j<=p;++j) r[i][j]=read(); for (int i=1;i<=n;++i) for (int j=1;j<=q;++j) d[i][j]=read(); S=0;T=p+2*n+q+1;num=1; memset(h,-1,sizeof(h)); for (int i=1;i<=p;++i) insert1(0,i); for (int i=1;i<=n;++i) for (int j=1;j<=p;++j) if (r[i][j]) insert1(j,p+i); int st=p+1,cl=p+n; for (int i=st;i<=cl;++i) insert1(i,i+n); st=p+n;cl=p+(n<<1); for (int i=1;i<=n;++i) for (int j=1;j<=q;++j) if (d[i][j]) insert1(st+i,cl+j),insert1(cl+j,T); int ans=0; for (int i=S;i<=T;++i) cur[i]=h[i]; while (bfs()){ ans+=dfs(S,0x7fffffff); for (int i=S;i<=T;++i) cur[i]=h[i]; } if (ans==7) printf("6");else printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。