Dining（最大流）

Dining

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

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 23462		Accepted: 10371

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 F_i and D_i, the number of dishes that cow i likes and the number of drinks that cow i likes. The next F_i integers denote the dishes that cow i will eat, and the D_i 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

Hint

One way to satisfy three cows is: 
Cow 1: no meal 
Cow 2: Food #2, Drink #2 
Cow 3: Food #1, Drink #1 
Cow 4: Food #3, Drink #3 
The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.

建图是关键。。。

把牛拆成两个点才能起到限流的作用

源点连食物，食物连牛in,牛in连牛out，牛out连饮料，饮料连汇点

 不能牛连食物，食物连饮料，不然食物可能会被使用一次以上，在这里想了半天，太菜了= =

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define maxn 100005
#define MAXN 100005
#define mem(a,b) memset(a,b,sizeof(a))
const int N=200005;
const int M=200005;
const int INF=0x3f3f3f3f;
using namespace std;
int n;
struct Edge{
    int v,next;
    int cap,flow;
}edge[MAXN*20];//注意这里要开的够大。。不然WA在这里真的想骂人。。问题是还不报RE。。
int cur[MAXN],pre[MAXN],gap[MAXN],path[MAXN],dep[MAXN];
int cnt=0;//实际存储总边数
void isap_init()
{
    cnt=0;
    memset(pre,-1,sizeof(pre));
}
void isap_add(int u,int v,int w)//加边
{
    edge[cnt].v=v;
    edge[cnt].cap=w;
    edge[cnt].flow=0;
    edge[cnt].next=pre[u];
    pre[u]=cnt++;
}
void add(int u,int v,int w){
    isap_add(u,v,w);
    isap_add(v,u,0);
}
bool bfs(int s,int t)//其实这个bfs可以融合到下面的迭代里，但是好像是时间要长
{
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]=1;
    dep[t]=0;
    queue<int>q;
    while(!q.empty())
    q.pop();
    q.push(t);//从汇点开始反向建层次图
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=pre[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(dep[v]==-1&&edge[i^1].cap>edge[i^1].flow)//注意是从汇点反向bfs，但应该判断正向弧的余量
            {
                dep[v]=dep[u]+1;
                gap[dep[v]]++;
                q.push(v);
                //if(v==sp)//感觉这两句优化加了一般没错，但是有的题可能会错，所以还是注释出来，到时候视情况而定
                //break;
            }
        }
    }
    return dep[s]!=-1;
}
int isap(int s,int t)
{
    if(!bfs(s,t))
    return 0;
    memcpy(cur,pre,sizeof(pre));
    //for(int i=1;i<=n;i++)
    //cout<<"cur "<<cur[i]<<endl;
    int u=s;
    path[u]=-1;
    int ans=0;
   // cout<<dep[s]<<" "<<n<<endl;
    while(dep[s]<n)//迭代寻找增广路
    {
        if(u==t)
        {
            int f=INF;
            for(int i=path[u];i!=-1;i=path[edge[i^1].v])//修改找到的增广路
                f=min(f,edge[i].cap-edge[i].flow);
            for(int i=path[u];i!=-1;i=path[edge[i^1].v])
            {
                edge[i].flow+=f;
                edge[i^1].flow-=f;
            }
            ans+=f;
            u=s;
            continue;
        }
        bool flag=false;
        int v;
        for(int i=cur[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].v;
            if(dep[v]+1==dep[u]&&edge[i].cap-edge[i].flow)
            {
                cur[u]=path[v]=i;//当前弧优化
                flag=true;
                break;
            }
        }
        if(flag)
        {
            u=v;
            continue;
        }
        int x=n;
        if(!(--gap[dep[u]]))return ans;//gap优化
        for(int i=pre[u];i!=-1;i=edge[i].next)
        {
            if(edge[i].cap-edge[i].flow&&dep[edge[i].v]<x)
            {
                x=dep[edge[i].v];
                cur[u]=i;//常数优化
            }
        }
        dep[u]=x+1;
        gap[dep[u]]++;
        if(u!=s)//当前点没有增广路则后退一个点
        u=edge[path[u]^1].v;
     }
     return ans;
}


int main(){
    int m,s,t;
    int F,D;
    scanf("%d %d %d",&n,&F,&D);
    int a,b,c;
    isap_init();
    int x1[105],x2[105];
    int f,d;
    for(int i=1;i<=n;i++){
        scanf("%d %d",&f,&d);
        for(int j=1;j<=f;j++){
            scanf("%d",&x1[j]);
            add(x1[j],F+i,1);
        }
        for(int j=1;j<=d;j++){
            scanf("%d",&x2[j]);
            for(int k=1;k<=f;k++){
                add(n+F+i,x2[j]+n+n+F,1);
            }
        }
    }
    for(int i=1;i<=F;i++){
        add(0,i,1);
    }
    for(int i=1;i<=n;i++){
        add(F+i,n+F+i,1);
    }
    for(int i=1;i<=D;i++){
        add(i+n+n+F,F+n+n+D+1,1);
    }
    s=0,t=F+n+n+D+1;
    n=F+n+n+D+2;
    printf("%d
",isap(s,t));
}


/*
2 2 2
2 1 1 2 1
1 1 1 2

2
*/