P1402 酒店之王

时间：2022-06-16 06:29:27

P1402 酒店之王

每个人要匹配一个A和一个B，所以这样连边：

S向每个房间连边。

每个房间向喜欢这个房间的人连边。

每个人向喜欢的菜连边。

每道菜向T连边。

边权均为1。

注意人要限流。

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<cstring>

#define il inline

#define rg register

#define vd void

#define sta static

typedef long long ll;

il int gi(){

    rg int x=0,f=1;rg char ch=getchar();

    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n;

const int maxn=403,S=401,T=402,maxm=1e7;

int fir[maxn],dis[maxm],nxt[maxm],w[maxm],id=1;

il vd link(int a,int b,int c){

    nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;

    nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0;

}

int dep[maxn];

il bool BFS(){

    sta int que[maxn],hd,tl;

    hd=tl=0;que[tl++]=S;

    memset(dep,-1,sizeof dep);

    dep[S]=1;

    while(hd^tl){

        int x=que[hd];

        for(rg int i=fir[x];i;i=nxt[i])

            if(w[i]&&dep[dis[i]]==-1){

                dep[dis[i]]=dep[x]+1;

                que[tl++]=dis[i];

            }

        ++hd;

    }

    return dep[T]!=-1;

}

il int Dinic(int x,int maxflow){

    if(x==T)return maxflow;

    int ret=0;

    for(rg int i=fir[x];i;i=nxt[i])

        if(w[i]&&dep[dis[i]]==dep[x]+1){

            int d=Dinic(dis[i],std::min(maxflow,w[i]));

            w[i]-=d;

            w[i^1]+=d;

            maxflow-=d;

            ret+=d;

            if(maxflow==0)break;

        }

    return ret;

}

int main(){

#ifdef xzz

    freopen("1402.in","r",stdin);

    freopen("1402.out","w",stdout);

#endif

    n=gi();

    int p=gi(),q=gi();

    for(rg int i=1;i<=p;++i)link(S,i,1);

    for(rg int i=1;i<=q;++i)link(i+300,T,1);

    for(rg int i=1;i<=n;++i)link(i+100,i+200,1);

    for(rg int i=1;i<=n;++i)for(rg int j=1;j<=p;++j)if(gi())link(j,i+100,1);

    for(rg int i=1;i<=n;++i)for(rg int j=1;j<=q;++j)if(gi())link(i+200,j+300,1);

    int ans=0;

    while(BFS())ans+=Dinic(S,1e9);

    printf("%d\n",ans);

    return 0;

}

相关文章