题解 P1402 【酒店之王】

2018-09-11 20:25:27


~~这么水真有省选/NOI-吗? 蒟蒻只用了24分钟就秒杀了~~

很明显的最大流(或者说二分图匹配)

不会最大流的可以去我的洛谷日报捧场

很显然要这么建图:

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的来捧场啊

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;
}