B - Dining POJ - 3281 （网络流 - 最大流 - 建图）

• 题目链接：https://vjudge.net/contest/68128#problem/B
• 题意：农场主有n头牛，有一天他做了F种food，D种drink，每头牛都有自己的喜好（food和drink的种类），每种food和drink都只能给一头牛。求如何使满足喜好的牛的数量最大。
• 思路：建图，即为最大流问题，直接用dinic解：
  

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <math.h>
#define pi acos(-1)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int INF = 0x3f3f3f3f;
const LL ll_INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 50000 + 10;
const int mod = 1e9 + 7;

int s, t;
int head[maxn], cnt=0;
int dis[maxn];
int n, f, d;

struct Edge
{
    int to, next, cap;
}es[maxn];

void init()
{
    memset(head, -1, sizeof(head));
}

void add(int u, int v)
{
    es[cnt].to = v;
    es[cnt].cap = 1;
    es[cnt].next = head[u];
    head[u] = cnt++;

    es[cnt].to = u;
    es[cnt].cap = 0;
    es[cnt].next = head[v];
    head[v] = cnt++;
}

bool BFS()
{
    queue<int> que;
    memset(dis, -1, sizeof(dis));
    dis[s] = 0;
    que.push(s);
    int cur, v;
    while(!que.empty())
    {
        cur = que.front(); que.pop();
        for(int i=head[cur]; i!=-1; i=es[i].next){
            v = es[i].to;
            if(dis[v]==-1 && es[i].cap>0){
                dis[v] = dis[cur]+1;
                que.push(v);
            }
        }
    }
    if(dis[t] == -1) return false;
    else return true;
}

int DFS(int cur, int low)
{
    int res=0;
    if(cur == t) return low;
    for(int i=head[cur]; i!=-1; i=es[i].next){
        if(dis[es[i].to]==dis[cur]+1
        && es[i].cap>0
        && (res = DFS(es[i].to, min(low, es[i].cap))) ){
            es[i].cap -= res;
            es[i^1].cap += res;
            return res;
        }
    }
    return 0;
}

int main()
{
    init();
    scanf("%d%d%d", &n, &f, &d);
    s = 0;
    t = 2*n+f+d+1;
    for(int i=1; i<=n; i++){
        int numf, numd, fv, dv;
        scanf("%d%d", &numf, &numd);
        for(int j=1; j<=numf; j++){
            scanf("%d", &fv);
            //add(s, fv);
            add(fv, f+i);
        }
        for(int j=1; j<=numd; j++){
            scanf("%d", &dv);
            //add(f+2*n+dv, t);
            add(f+n+i, f+2*n+dv);
        }
        //add(f+i, f+n+i);
    }
    for(int i=1; i<=f; i++){
        add(s, i);
    }
    for(int i=1; i<=n; i++){
        add(f+i, f+n+i);
    }
    for(int i=1; i<=d; i++){
        add(f+2*n+i, t);
    }
    int ans=0 , tmp=0;
    while(BFS()){
        if(tmp = DFS(s, INF))
            ans += tmp;
    }
    printf("%d\n", ans);
}