Loading...

洛谷P1402 酒店之王

check评论:0 条 remove_red_eye浏览量:164 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-08-03

题目链接

  • 题目描述

$XX$酒店的老板想成为酒店之王,本着这种希望,第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等,也有自己所爱的菜,但是该酒店只有$p$间房间,一天只有固定的$q$道不同的菜。

有一天来了$n$个客人,每个客人说出了自己喜欢哪些房间,喜欢哪道菜。但是很不幸,可能做不到让所有顾客满意(满意的条件是住进喜欢的房间,吃到喜欢的菜)。

这里要怎么分配,能使最多顾客满意呢?

  • 题目分析

这显然是一道最大流,考虑到一个人要满意必须同时满足房间和菜品他都喜欢,如果我们仍将菜品或房间作为中间点,他们就变成了并列条件,与题意不符,故我们将人看作中间点

如果此时直接写最大流会发现无法通过,原因如下图

eDwnje.md.png

其中$1,7$分别是源点与汇点,$4$是人,$2,3$是房间,$5,6$是菜品,你会发现,这组数据答案应该是$1$,可是最大流跑出来是$2$

原因就是我们没有限制流过$1$个人的流最多为$1$

考虑建一个新点,如图,这样就完美的解决了问题

eDwmcD.md.png

  • 代码实现
/**************************/
/*It is made by decoration*/
/*gzzkal   gzzkal   gzzkal*/
/*It is made by decoration*/
/**************************/
#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int next,to,dis;
}e[10000100];
int head[5000100],dis[5000100],vis[5000100],cur[5000100],n,p,q;
int s=0,t,cnt=1;
void add(int u,int v,int dis)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
}
int bfs()
{
    queue<int> q;
    memcpy(cur,head,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(dis,-1,sizeof(dis));
    dis[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]==-1&&e[i].dis>0)
            {
                dis[v]=dis[u]+1;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dis[t]!=-1;
}
int dfs(int u,int ex)
{
    if(u==t||!ex)
    {
        return ex;
    }
    int flow=0;
    for(int &i=cur[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(dis[v]==dis[u]+1&&e[i].dis>0)
        {
            int tmp=dfs(v,min(ex,e[i].dis));
            if(!tmp)        
            {
                continue;
            }
            ex-=tmp,flow+=tmp;
            e[i].dis-=tmp,e[i^1].dis+=tmp;
            if(!ex)
            {
                break;
            }
        }
    }
    return flow;
}
int main()
{
    cin>>n>>p>>q;
    t=n+n+p+q+1;
    for(int i=1;i<=p;i++)
    {
        add(s,i,1);
        add(i,s,0);
    }
    for(int i=1;i<=q;i++)
    {
        add(i+n+n+p,t,1);
        add(t,i+n+n+p,0);
    }
    for(int i=1;i<=n;i++)
    {
        add(i+p,i+n+p,1);
        add(i+n+p,i+p,0);
        for(int x,j=1;j<=p;j++)
        {
            scanf("%d",&x);
            if(x)
            {
                add(j,i+p,1);
                add(i+p,j,0);
            }
        }
    }    
    for(int i=1;i<=n;i++)
    {
        for(int x,j=1;j<=q;j++)
        {
            scanf("%d",&x);
            if(x)
            {
                add(i+n+p,p+n+n+j,1);
                add(p+n+n+j,i+n+p,0);
            }
        }
    }
    int ans=0;
    while(bfs())
    {
        ans+=dfs(s,0x3f3f3f3f);
    }
    cout<<ans;
}

chevron_left 数论小结

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名