题解 P1402 【酒店之王】

~~这么水真有省选/NOI-吗？ 蒟蒻只用了24分钟就秒杀了~~~~~~ ## 很明显的最大流（或者说二分图匹配） 不会最大流的[可以去我的洛谷日报捧场](https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-di-zong-jie) ## 很显然要这么建图： ## s流向房间，房间流向顾客，顾客流向菜，菜流向t，每条边流量限制为1，然后跑最大流。 然而这样可能会错： 请看下图:  某顾客一个人霸占了两个房间和两个菜，导致最大流为2（实际应该为1，因为只满足了1个顾客）的情况，我们要限制每个顾客只用一个房间和一个菜 怎么限制呢？ # 主要思想：拆点 为什么？~~刷水题刷多了就很自然的会这么想~~ 为了限制容量。 什么意思？ 每个顾客肯定只能住一间房间和吃一道菜： 所以我们把一个顾客拆成两个点：入点和出点，然后连一条入点到出点的边，容量限制为1，这样每个顾客就最多只经过一次了，跑出来的最大流就是正解。 刚才那张图拆了点就是这样：  图画的很丑，但还是能看懂的（应该吧） ------------ 然后就是代码了 ## 我写的EK： ``` #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> using namespace std; const int inf=1<<30; inline int Read(){ int x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*f; } int n,p,q,s,t; struct Node{ int v; int val; int next; }node[101101]; int head[1010],top=1; inline void addedge(int u,int v,int val){ node[++top].v=v; node[top].val=val; node[top].next=head[u]; head[u]=top; } inline void add(int u,int v,int val){ addedge(u,v,val); addedge(v,u,0); } int vis[1010]; struct P{ int fa; int pos; }pre[101011]; bool bfs(){ memset(vis,0,sizeof(vis)); queue<int>q; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=node[i].next){ int d=node[i].v; if(node[i].val!=0&&vis[d]==0){ pre[d].fa=u; pre[d].pos=i; if(d==t)return 1; q.push(d); vis[d]=1; } } } return 0; } int maxflow=0; int EK(){ maxflow=0; int mi; while(bfs()){ mi=inf; for(int i=t;i!=s;i=pre[i].fa) mi=min(mi,node[pre[i].pos].val); for(int i=t;i!=s;i=pre[i].fa){ node[pre[i].pos].val-=mi; node[pre[i].pos^1].val+=mi; } maxflow+=mi; } return maxflow; } int main(){ n=Read(),p=Read(),q=Read(); register int i,j; int f; s=1001,t=1002; for(i=1;i<=n;i++)add(i,i+n,1);//i表示顾客入点，i+n表示顾客出点 for(i=1;i<=p;i++)add(s,200+i,1);//200+i表示房间 for(i=1;i<=q;i++)add(300+i,t,1);//300+i表示菜 for(i=1;i<=n;i++){ for(j=1;j<=p;j++){ f=Read(); if(f==1)add(200+j,i,1); } } for(i=1;i<=n;i++){ for(j=1;j<=q;j++){ f=Read(); if(f==1)add(i+n,300+j,1); } } printf("%d",EK()); return 0; } ``` ------------ ## 二分图中EK不够高效，于是我们还可以选择Dinic [不会DInic的来捧场啊](https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-jiang-xie-zhi-dinic) Dinic代码： ``` #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> using namespace std; const int inf=1<<30; inline int Read(){ int x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*f; } int n,p,q,s,t; struct Node{ int v; int val; int next; }node[101101]; int head[1010],top=1; inline void addedge(int u,int v,int val){ node[++top].v=v; node[top].val=val; node[top].next=head[u]; head[u]=top; } inline void add(int u,int v,int val){ addedge(u,v,val); addedge(v,u,0); } int inque[1010],dep[1010]; bool bfs(){ memset(inque,0,sizeof(inque)); memset(dep,0x3f,sizeof(dep)); queue<int>q; q.push(s); dep[s]=0; while(!q.empty()){ int u=q.front(); q.pop(); inque[u]=0; for(int i=head[u];i;i=node[i].next){ int d=node[i].v; if(node[i].val&&dep[d]>dep[u]+1){ dep[d]=dep[u]+1; if(inque[d]==0){ q.push(d); inque[d]=1; } } } } return dep[t]!=0x3f3f3f3f; } int maxflow=0; int vis; int dfs(int u,int flow){ if(u==t){ vis=1; maxflow+=flow; return flow; } int used=0; for(int i=head[u];i;i=node[i].next){ int d=node[i].v; if(node[i].val&&dep[d]==dep[u]+1){ int mi=dfs(d,min(node[i].val,flow-used)); if(mi){ node[i].val-=mi; node[i^1].val+=mi; used+=mi; } } if(used==flow)break; } return used; } int Dinic(){ maxflow=0; while(bfs()){ vis=1; while(vis)vis=0,dfs(s,inf); } return maxflow; } int main(){ n=Read(),p=Read(),q=Read(); register int i,j; int f; s=1001,t=1002; for(i=1;i<=n;i++)add(i,i+n,1);//i表示顾客入点，i+n表示顾客出点 for(i=1;i<=p;i++)add(s,200+i,1);//200+i表示房间 for(i=1;i<=q;i++)add(300+i,t,1);//300+i表示菜 for(i=1;i<=n;i++){ for(j=1;j<=p;j++){ f=Read(); if(f==1)add(200+j,i,1); } } for(i=1;i<=n;i++){ for(j=1;j<=q;j++){ f=Read(); if(f==1)add(i+n,300+j,1); } } printf("%d",Dinic()); return 0; } ``` ------------ ## Dinic还有当前弧优化（不过这题数据实在太水，体现不出优势）： ``` #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> using namespace std; const int inf=1<<30; inline int Read(){ int x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*f; } int n,p,q,s,t; struct Node{ int v; int val; int next; }node[101101]; int head[1010],top=1; inline void addedge(int u,int v,int val){ node[++top].v=v; node[top].val=val; node[top].next=head[u]; head[u]=top; } inline void add(int u,int v,int val){ addedge(u,v,val); addedge(v,u,0); } int inque[1010],dep[1010],cur[1010]; bool bfs(){ register int i; for(i=1;i<=t;i++)dep[i]=inf,inque[i]=0,cur[i]=head[i]; queue<int>q; q.push(s); dep[s]=0; while(!q.empty()){ int u=q.front(); q.pop(); inque[u]=0; for(i=head[u];i;i=node[i].next){ int d=node[i].v; if(node[i].val&&dep[d]>dep[u]+1){ dep[d]=dep[u]+1; if(inque[d]==0){ q.push(d); inque[d]=1; } } } } return dep[t]!=inf; } int maxflow=0; int vis; int dfs(int u,int flow){ if(u==t){ vis=1; maxflow+=flow; return flow; } int used=0; for(int i=cur[u];i;i=node[i].next){ cur[u]=i; int d=node[i].v; if(node[i].val&&dep[d]==dep[u]+1){ int mi=dfs(d,min(node[i].val,flow-used)); if(mi){ node[i].val-=mi; node[i^1].val+=mi; used+=mi; } } if(used==flow)break; } return used; } int Dinic(){ maxflow=0; while(bfs()){ vis=1; while(vis)vis=0,dfs(s,inf); } return maxflow; } int main(){ n=Read(),p=Read(),q=Read(); register int i,j; int f; s=401,t=402; for(i=1;i<=n;i++)add(i,i+n,1);//i表示顾客入点，i+n表示顾客出点 for(i=1;i<=p;i++)add(s,200+i,1);//200+i表示房间 for(i=1;i<=q;i++)add(300+i,t,1);//300+i表示菜 for(i=1;i<=n;i++){ for(j=1;j<=p;j++){ f=Read(); if(f==1)add(200+j,i,1); } } for(i=1;i<=n;i++){ for(j=1;j<=q;j++){ f=Read(); if(f==1)add(i+n,300+j,1); } } printf("%d",Dinic()); return 0; } ```