Poj 3281 Dining

http://poj.org/problem?id=3281

题意：约翰给他的牛准备F种食物和D种饮料（约翰和牛，Alice和Bob……）每头牛都有自己喜欢的食物和饮料，而每种食物和饮料只能分配给一头牛。最多能有多少头牛能同时分配到喜欢的食物和饮料。

题解：最大流的模型之一，要用到所谓的拆点。除了牛、食物和饮料之外建立s和t，把牛的数量*2，两个分配相同的牛之间连边。连边顺序：s->食物->牛->牛->饮料->t。

注意：输入lf[][]、ld[][]时要注意t-1，因为题目数据是从1开始计数的。用小兰的话说：“好无赖啊……”。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <fstream>

using namespace std;

const int INF=100000000;
const int maxn=2100;
int lf[maxn][maxn],ld[maxn][maxn];
struct edge{
    int to,cap,rev;
};
vector<edge> G[maxn];
int level[maxn];
int iter[maxn];

void add_edge(int from,int to,int cap)
{
    G[from].push_back((edge){to,cap,(int)G[to].size()});
    G[to].push_back((edge){from,0,(int)G[from].size()-1});
}

void bfs(int s)
{
    memset(level, -1, sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while (!que.empty()) {
        int v=que.front();
        que.pop();
        for (int i=0; i<G[v].size(); i++) {
            edge &e=G[v][i];
            if (e.cap>0&&level[e.to]<0) {
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v,int t,int f)
{
    if (v==t) {
        return f;
    }
    for (int &i=iter[v]; i<G[v].size(); i++) {
        edge &e=G[v][i];
        if (e.cap>0 && level[v]<level[e.to]) {
            int d=dfs(e.to, t, min(f,e.cap));
            if (d>0) {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s,int t)
{
    int flow=0;
    for (;;) {
        bfs(s);
        if (level[t]<0) {
            return flow;
        }
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f=dfs(s, t, INF))>0) {
            flow+=f;
        }
    }
}
int main()
{
    //freopen("/Users/apple/Desktop/poj 3281/poj 3281/in", "r", stdin);
    //freopen("/Users/apple/Desktop/poj 3281/poj 3281/out", "w", stdout);
    int N,F,D;
    memset(lf, 0, sizeof(lf));
    memset(ld, 0, sizeof(ld));
    scanf("%d%d%d",&N,&F,&D);
    int fi,di,fj,dk;
    for (int i=0; i<N; i++) {
        scanf("%d%d",&fi,&di);
        for (int j=0; j<fi; j++) {
            //scanf("%d",&lf[i][j]);
            scanf("%d",&fj);
            lf[i][fj-1]=1;
        }
        for (int k=0; k<di; k++) {
            //scanf("%d",&ld[i][k]);
            scanf("%d",&dk);
            ld[i][dk-1]=1;
        }
    }
    
    //0~N-1食物与牛
    //N~N*2-1饮料与牛
    //N*2~N*2+F-1食物
    //N*2+F~N*2+F+D-1饮料
    int s=N*2+F+D,t=s+1;
    
    for (int i=0; i<F; i++) {
        add_edge(s, N*2+i, 1);
    }
    for (int i=0; i<D; i++) {
        add_edge(N*2+F+i, t, 1);
    }
    for (int i=0; i<N; i++) {
        add_edge(i, N+i, 1);
        for (int j=0; j<F; j++) {
            if (lf[i][j]) {
                add_edge(N*2+j, i, 1);
            }
        }
        for (int k=0; k<D; k++) {
            if (ld[i][k]) {
                add_edge(N+i, N*2+F+k, 1);
            }
        }
    }
    
    printf("%d
",max_flow(s, t));
    
    return 0;
}