[luogu1402]酒店之王_网络流

酒店之王 luogu-1402

　　　　题目大意：有n个人，p道菜，q个房间，每个人喜欢吃一些菜、喜欢住一些房间，如果一个人即住到了他喜欢的房间有吃到了他喜欢的菜，就对答案贡献++，求最大贡献。

　　　　注释：1<=n,p,q<=100.

　　　　　　想法：网络流第二题，和上一题相比有一条比较重要的限制就是每个人最多只能对答案贡献1，所以，我们对于一个相同的人加两个相同的节点，之间的流量为1。第一个人联想喜欢的菜，第二个人连向喜欢的房间，所有的菜指向源点，所有的菜指向汇点。这样每一个从源点到汇点的完整流必定为1且满足题意。

　　　　最后，附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
int head[51000],to[101000],nxt[101000],tot=1,dis[51000],all;
int f[101000];
inline void add(int x,int y,int z)
{
    to[++tot]=y;
    f[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
}
bool bfs()
{
    queue<int>q;
    memset(dis,-1,sizeof dis);
    while(!q.empty()) q.pop();
    q.push(1);dis[1]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nxt[i])if(f[i]&&dis[to[i]]==-1)
        {
            dis[to[i]]=dis[x]+1;
            q.push(to[i]);
            if(to[i]==all) return true;
        }
    }
    return false;
}
int dinic(int x,int flow)
{
    int a,temp=flow;
    if(x==all) return flow;
    for(int i=head[x];i;i=nxt[i])
    {
        if(f[i]>0&&dis[to[i]]==dis[x]+1)
        {
            a=dinic(to[i],min(f[i],temp));
            if(a==0) dis[to[i]]=-1;
            temp-=a;
            f[i]-=a;
            f[i^1]+=a;
            if(temp==0) break;
        }
    }
    return flow-temp;
}
int main()
{
    int n,p,q;
    cin >> n >> p >> q;
    all=1+p+2*n+q+1;
    // cout << all << endl;
    for(int i=1;i<=p;i++)
    {
        add(1,i+1,1);
        add(i+1,1,0);
    }
    // puts("Fuck1");
    for(int a,i=1;i<=n;i++)
    {
        for(int j=1;j<=p;j++)
        {
            cin >> a;
            if(a)
            {
                add(1+j,1+p+i,1);
                add(1+p+i,1+j,0);
            }
            else 
            {
                add(1+j,1+p+i,0);
                add(1+p+i,1+j,0);
            }
        }
    }
    // puts("Fuck2");
    for(int i=1;i<=n;++i)
    {
        add(1+p+i,1+p+n+i,1);
        add(1+p+n+i,1+p+i,0);
    }
    // puts("Fuck3");
    for(int a,i=1;i<=n;i++)
    {
        for(int j=1;j<=q;j++)
        {
            cin >> a;
            if(a)
            {
                add(1+p+n+i,1+p+2*n+j,1);
                add(1+p+2*n+j,1+p+n+i,0);
            }
            else
            {
                add(1+p+n+i,1+p+2*n+j,0);
                add(1+p+2*n+j,1+p+n+i,0);
            }
        }
    }
    // puts("Fuck4");
    for(int i=1;i<=q;i++)
    {
        add(1+p+2*n+i,all,1);
        add(all,1+p+2*n+i,0);
    }
    ll ans=0;
    // puts("Fuck5");
    while(bfs())
    {
        // puts("Fuck6");
        ans+=dinic(1,inf);
    }
    printf("%lld
",ans);
    return 0;
}

 　　　　小结：这个技巧非常重要。