POJ 3281 Dining(网络流经典构图)

红太狼 2022-05-16 23:19 159阅读 0赞

[题目链接][Link 1]

题目大意：农夫John有N头牛，每头牛都有自己喜欢的食物和水的种类，一共有F种食物和D种水，现在让你来进行分配，每种食物或水只能分配给一头牛，并且每头牛只能得到一种食物和一种水，问最多能使几头牛同时享用到自己喜欢的食物和饮料。（1 <= N <= 100, 1 <= F <= 100, 1 <= D <= 100）

分析：这题第一反应很容易往二分图匹配想，但是因为现在有食物和水两种东西，且必须同时满足，那么很明显二分图匹配是不行的，看了网上的题解，不得不佩服这些神犇，这题是用的最大流来做的，设置一个源点和一个终点，将食物和水放在两端，将每头牛拆成两个点放在中间。**最大流的正确性依赖于它的每一条s->t流都与一种实际方案一一对应**。此题需要用s-t流将一头牛和它喜欢的食物和饮料连接，而食物和饮料之间没有直接关系，自然就想到把牛放在中间，两边是食物和饮料，即s->食物->牛->饮料->t，每条边的权值都为1，故如果形成一条这样的流，就构成一种分配方案。但是还要考虑每头牛是唯一的，故需要考虑牛这个点的权值为1的问题，这时就用到拆点。

![70][]

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 5e2+7;
    const int inf = 0x3f3f3f3f;
    int pre[maxn],cap[maxn][maxn],flow[maxn];
    int vs,ed;
    
    void CLEAR(queue<int>&q)
    {
        queue<int>q1;
        swap(q1,q);
    }
    
    int BFS()
    {
        queue<int>q;
        CLEAR(q);
        memset(pre,-1,sizeof(pre));
        pre[vs]=0;
        flow[vs]=inf;
        q.push(vs);
        while(!q.empty())
        {
            int index=q.front();
            q.pop();
            rfup(i,0,ed)
            {
                if(i!=vs&&pre[i]==-1&&cap[index][i])
                {
                    pre[i]=index;
                    flow[i]=min(cap[index][i],flow[index]);
                    q.push(i);
                }
            }
        }
        if(pre[ed]==-1)//如果找不到增广路
            return -1;
        return flow[ed];
    }
    
    int maxflow()
    {
        int sum=0;
        int add,last,now;
        while((add=BFS())!=-1)
        {
            int now=ed;
            while(now!=vs)
            {
                last=pre[now];
                cap[last][now]-=add;
                cap[now][last]+=add;
                now=last;
            }
            sum+=add;
        }
        return sum;
    }
    
    int main()
    {
        int N,F,D;
        while(scanf("%d%d%d",&N,&F,&D)!=EOF)
        {
            Clear(cap),Clear(flow);
            vs=0;ed=F+2*N+D+1;
            rfup(i,1,F) cap[vs][i]=1;
            rfup(i,F+2*N+1,F+2*N+D) cap[i][ed]=1;
            rfup(i,1,N) cap[F+2*i-1][F+2*i]=1;
            int a,b,u;
            rfup(i,1,N)
            {
                scanf("%d%d",&a,&b);
                while(a--)
                {
                    scanf("%d",&u);
                    cap[u][F+2*i-1]=1;
                }
                while(b--)
                {
                    scanf("%d",&u);
                    cap[F+2*i][F+2*N+u]=1;
                }
            }
            printf("%d\n",maxflow());
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=3281
[70]: /images/20220517/5c294b1ac39b46eab8697de5cdbfafdb.png