LGP2891题解

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目大意

有 \(n\) 只奶牛，\(q\) 种食物和 \(p\) 种饮料，每只奶牛喜欢一些饮料和食物，但只能那一种，求最小配对数量。

首先来看一下这道题的简化版：没有饮料，该怎么做呢？

我会！裸的二分图最大匹配！

但加了饮料，就有了两种限制条件，我们自然地想到直接饮料、食物和奶牛都连边，用Dinic跑网络最大流。

于是你WA了。

问题处在哪儿呢？

让我们来看一组数据：

1 2 2

2 2 1 2 1 2

用Dinic跑网络最大流，答案是2，但正确答案是1。

问题在于：同一只奶牛选了两次。

所以我们运用拆点的思想，将一只奶牛拆成两个点：出点和入点，食物连入点，出点连饮料。

然后你再交上去就A了qwq

给一下代码吧：

#include<cstring>

#include<cstdio>

#include<queue>

const int M=405;

struct Edge{

    int to,nx,flow;

}e[M*200];

int n,q,p,s,t,cnt=1,d[M],h[M],cur[M];

inline int min(const int a,const int b){

    return a>b?b:a;

}

inline void Add(int x,int y){

    e[++cnt]=(Edge){y,h[x],1};h[x]=cnt;

    e[++cnt]=(Edge){x,h[y],0};h[y]=cnt;

}

inline bool BFS(){

    register int E,u,v;

    std::queue<int>q;

    memset(d,0,sizeof d);

    q.push(s);d[s]=1;

    while(!q.empty()){

        u=q.front();q.pop();

        for(E=cur[u]=h[u];E;E=e[E].nx)if(e[E].flow){

            v=e[E].to;

            if(!d[v]){

                d[v]=d[u]+1;

                q.push(v);

            }

        }

    }

    return d[t];

}

int DFS(register int u,register int flow){

    if(u==t)return flow;

    int used=flow;

    for(register int&E=cur[u];E;E=e[E].nx)if(e[E].flow){

        int v=e[E].to;

        if(d[v]==d[u]+1){

            int f=DFS(v,min(used,e[E].flow));

            e[E].flow-=f;e[E^1].flow+=f;used-=f;

            if(!f)d[v]=0;

            if(!used)return flow;

        }

    }

    return cur[u]=h[u],flow-used;

}

inline int Dinic(){

    int ans=0;

    while(BFS())while(int d=DFS(s,2e9))ans+=d;

    return ans;

}

signed main(){

    int i,j,u,x,y;

    scanf("%d%d%d",&n,&q,&p);

    s=0;t=q+n+n+p+1;

    for(i=1;i<=q;++i)Add(s,i);

    for(i=1;i<=n;++i)Add(q+i,q+n+i);

    for(i=1;i<=p;++i)Add(q+n+n+i,t);

    for(i=1;i<=n;++i){

        scanf("%d%d",&x,&y);

        for(j=1;j<=x;++j){

            scanf("%d",&u);

            Add(u,q+i);

        }

        for(j=1;j<=y;++j){

            scanf("%d",&u);

            Add(q+n+i,q+n+n+u);

        }

    }

    printf("%d",Dinic());

}