图论--网络流--最大流--POJ 3281 Dining (超级源汇+限流建图+拆点建图）

风骨散人Chiam

发布于 2020-10-28 11:32:27

4110

发布于 2020-10-28 11:32:27

文章被收录于专栏：CSDN旧文

Description

Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.

Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible.

Farmer John has cooked F (1 ≤ F ≤ 100) types of foods and prepared D (1 ≤ D ≤ 100) types of drinks. Each of his N (1 ≤ N ≤ 100) cows has decided whether she is willing to eat a particular food or drink a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both.

Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2).

Input

Line 1: Three space-separated integers: N, F, and D Lines 2..N+1: Each line i starts with a two integers Fi and Di, the number of dishes that cow i likes and the number of drinks that cow i likes. The next Fi integers denote the dishes that cow i will eat, and the Di integers following that denote the drinks that cow i will drink.

Output

Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes

Sample Input

4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3

Sample Output

3
题意：每头牛都有爱吃的食物和饮料。每头牛只能吃一个食物一瓶饮料，饮料与食物最多被吃一次，问你最多有多少头牛能够吃的喜欢的食物且喝到自己喜欢的饮料。

这个题大家都会想到，如果设置一个源点，一个汇点，建图如下：

这样设置边的容量1，然后网络流即可到这里，大家还都能听明白吧，因为这样走必然会经过一个食物和饮料，但是有一个问题是什么，因为每头牛只能喝一瓶吃一个食物，所以这里要将牛拆点，通过拆点后可 i和i'添加 i--i '的权值为1的边达到限流建图的目的，然后跑一边的最大流即可。

//RQ的板子真的很好用

#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstring>
//---------------------------------Sexy operation--------------------------//

#define cini(n) scanf("%d",&n)
#define cinl(n) scanf("%lld",&n)
#define cinc(n) scanf("%c",&n)
#define cins(s) scanf("%s",s)
#define coui(n) printf("%d",n)
#define couc(n) printf("%c",n)
#define coul(n) printf("%lld",n)
#define debug(n) printf("%d_________________________________\n",n);
#define speed ios_base::sync_with_stdio(0)
#define file  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
//-------------------------------Actual option------------------------------//
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Swap(a,b) a^=b^=a^=b
#define Max(a,b) (a>b?a:b)
#define Min(a,b) a<b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define mp(a,b) make_pair(a,b)
#define pb(n)  push_back(n)
#define dis(a,b,c,d) ((double)sqrt((a-c)*(a-c)+(b-d)*(b-d)))
//--------------------------------constant----------------------------------//

#define INF  0x3f3f3f3f
#define esp  1e-9
#define PI   acos(-1)
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef  long long ll;
//___________________________Dividing Line__________________________________/
#define maxn 500+5


struct Edge
{
    int from,to,cap,flow;
    Edge(){}
    Edge(int f,int t,int c,int flow):from(f),to(t),cap(c),flow(flow){}
};

struct Dinic
{
    int n,m,s,t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int cur[maxn];
    int d[maxn];

    void init(int n,int s,int t)
    {
        this->n=n, this->s=s, this->t=t;
        edges.clear();
        for(int i=1;i<=n;i++) G[i].clear();
    }

    void AddEdge(int from,int to,int cap)
    {
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int> Q;
        d[s]=0;
        Q.push(s);
        vis[s]=true;
        while(!Q.empty())
        {
            int x=Q.front(); Q.pop();
            for(int i=0;i<G[x].size();i++)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to] && e.cap>e.flow)
                {
                    vis[e.to]=true;
                    Q.push(e.to);
                    d[e.to]= 1+d[x];
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a)
    {
        if(x==t || a==0) return a;
        int flow=0,f;
        for(int& i=cur[x]; i<G[x].size(); i++)
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow) ))>0 )
            {
                e.flow+=f;
                edges[G[x][i]^1].flow -=f;
                flow+=f;
                a-=f;
                if(a==0) break;
            }
        }
        return flow;
    }

    int Maxflow()
    {
        int flow=0;
        while(BFS())
        {
            memset(cur,0,sizeof(cur));
            flow += DFS(s,INF);
        }
        return flow;
    }
}DC;

int main()
{
    int N,D,F;
    while(scanf("%d%d%d",&N,&F,&D)==3)
    {
        int T=N*2+D+F+1;
        DC.init(T+1,0,T);
        for(int i=1;i<=N;i++)
        {
            int FN,DN,tem;
            cini(FN),cini(DN);
            while(FN--)
            {
                cini(tem);
                DC.AddEdge(tem+N*2,i,1);
            }
            while(DN--)
            {
                cini(tem);
                DC.AddEdge(N+i,tem+F+N*2,1);
            }
            DC.AddEdge(i,N+i,1);
        }
        for(int i=1;i<=F;++i)
        {
            DC.AddEdge(0,i+N*2,1);
        }
        for(int i=1;i<=D;++i)
        {
            DC.AddEdge(i+N*2+F,T,1);
        }
        printf("%d\n",DC.Maxflow());
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/11/03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

each