[题解]P1402 |酒店之王

题目链接

其实这道题和某道P1231 教辅的组成几乎是双倍经验，考点也一样

分析

这道题是一道最大匹配问题，结合数据范围可以很容易的想到网络流

我们发现酒店的房间和菜都是和人有关的，所以我们把人和房间、菜分别连边，并且从原点s向
房间连边，菜向汇点连边

但是每一个顾客的贡献只能计算一次，
也就是只能和一道菜和一个房间匹配。

如果像上面那样连边会造成错误，如：

X点的贡献变成了2，实际应是1

所以我们考虑将代表人的点拆开，分为两组，
一组为入点，一组为出点

房间向入点连边，出点向菜连边，入点和出点之间连边

所有的边流量为1，代表只能使用一次
即：

\(\begin{aligned}&S\xrightarrow{1}P_{room}\\&P_{meal}\xrightarrow{1}T \\&P_{room}\xrightarrow{1}P_{people}.in\\&P_{people}.out\xrightarrow{1}P_{meal}\\&P_{people}.in\xrightarrow{1}P_{people}.out\end{aligned}\)

代码

\(\mathcal{Code:}\)

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
#define int long long
#define debug cout<<__LINE__<<" "<<__FUNCTION__<<"\n"
inline int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*y;
}
int n_1,n_2,n_3,m_1,m_2,s,t,dep[N];
int head[N],used[N],tot=1,front;//tot赋1方便找反向边
int ans;
struct Node{
    int nxt,to,dis;
}edge[N<<1];
inline void add(int x,int y,int z){
    edge[++tot].nxt=head[x];
    edge[tot].to=y;
    edge[tot].dis=z;
    head[x]=tot;
}
queue<int> q;
inline int bfs(){
    register int i;
    for(i=0;i<=n_1+n_1+n_2+n_3+2;i++) dep[i]=-1,used[i]=head[i];
    //记得在初始化时一定算好大小点的数量
    dep[s]=0;
    q.push(s);
    while(!q.empty()){
        front=q.front();q.pop();
        for(i=head[front];i;i=edge[i].nxt){
            if(edge[i].dis&&dep[edge[i].to]==-1){
                dep[edge[i].to]=dep[front]+1;q.push(edge[i].to);
            }
        }
    }
    return dep[t]!=-1;
}
int dfs(int now,int limit){
    if(!limit||now==t) return limit;
    int flow=0;
    for(int &i=used[now],pro;i;i=edge[i].nxt){
        if(dep[edge[i].to]==dep[now]+1&&(pro=dfs(edge[i].to,min(limit,edge[i].dis)))){
            edge[i].dis-=pro;
            edge[i^1].dis+=pro;
            flow+=pro;
            limit-=pro;
        }
    }
    return flow;
}
inline void Dinic(){//最大流板子
    while(bfs()) ans+=dfs(s,1000000001LL);
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    n_1=read();n_2=read();n_3=read();//people room meal
    s=0;t=n_1+n_1+n_2+n_3+1;//S和T的取值(个人习惯)
    register int i,j,u;
    for(i=n_1+n_1+1;i<=n_1+n_1+n_2;i++){//从S到P_room
        add(s,i,1);add(i,s,0);
    }
    for(i=n_1+n_1+n_2+1;i<=n_1+n_1+n_2+n_3;i++){//从P_meal到T
        add(i,t,1);add(t,i,0);
    }
    for(i=1;i<=n_1;i++){//从P_people.in到P_people.out
        add(i,i+n_1,1);add(i+n_1,i,0);
    }
    for(i=1;i<=n_1;i++){//从P_room到P_people.in
        for(j=1;j<=n_2;j++){
            u=read();
            if(u){
                add(j+n_1+n_1,i,1);add(i,j+n_1+n_1,0);
            }
        }
    }
    for(i=1;i<=n_1;i++){//从P_people.out到P_meal
        for(j=1;j<=n_3;j++){
            u=read();
            if(u){
                add(i+n_1,j+n_1+n_1+n_2,1);add(j+n_1+n_1+n_2,i+n_1,0);
            }
        }
    }
    Dinic();
    cout<<ans<<"\n";
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}