poj 3281 Dining//SAP

Dining
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 3803
 
Accepted: 1723
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

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.
Source
USACO 2007 Open Gold
이전에 한 제목을 뜯어보면 어떤 것은 무방향도이기 때문이고, 어떤 것은 회류를 방지하기 때문이다
이번에 이 문제의 해체는 소 한 마리당 정식을 하나만 먹을 수 있기 때문이다.
이것은 매우 관건적인 요소로 이 요소도 이분도 일치의 응용을 제한한다
나는 어느 고수가 이분도로 이 문제를 풀었는지 모르겠지만, 이분도로 그림을 만들 때 이 조건의 제약을 받아 인터넷으로 흐르는 방법을 찾으러 갔다
 
구도는 역시 비교적 간단하다
왼쪽에 음식을 넣고 오른쪽에 음료수를 넣는 것을 쉽게 얻을 수 있다
처음에 내가 이분도로 만들었을 때, 바로 소의 취향에 따라 음식과 음료수를 연결시켰다
나중에 이분도라는 길이 막혀서 SAP를 사용할 때 관건은 위의 소 한 마리당 한 세트만 먹는 조건을 충족시키는 것이 되었다.
그럼 어떻게 만족하지?
맞아요. 소를 뜯고 i, i+f를 뜯고 두 점 사이에 1을 연습해서 소 한 마리당 한 번만 먹을 수 있도록 해요.
다른 것은 원점이 음식으로 연결되어 있고 가장자리는 1이다.음료수 연방향 송금점, 가장자리 길이 1.
구도는 바로 이렇다. 비교적 간단하다
 
만약 이분도로 이 문제를 어떻게 통과했는지 아는 사람이 있다면, 나에게 한마디 해라. 고맙다
 
#include
#include
const int N=510;
const int M=100001;
const int inf=0x7fffffff;
int head[N];
struct Edge
{
    int v,next,w;
} edge[M];
int cnt,n,s,t;
void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].w=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
int sap()
{
    int pre[N],cur[N],dis[N],gap[N];
    int flow=0,aug=inf,u;
    bool flag;
    for(int i=0; i    {
        cur[i]=head[i];
        gap[i]=dis[i]=0;
    }
    gap[s]=n;
    u=pre[s]=s;
    while(dis[s]    {
        flag=0;
        for(int &j=cur[u]; j!=-1; j=edge[j].next)
        {
            int v=edge[j].v;
            if(edge[j].w>0&&dis[u]==dis[v]+1)
            {
                flag=1;
                if(edge[j].w                pre[v]=u;
                u=v;
                if(u==t)
                {
                    flow+=aug;
                    while(u!=s)
                    {
                        u=pre[u];
                        edge[cur[u]].w-=aug;
                        edge[cur[u]^1].w+=aug;
                    }
                    aug=inf;
                }
                break;
            }
        }
        if(flag) continue;
        int mindis=n;
        for(int j=head[u]; j!=-1; j=edge[j].next)
        {
            int v=edge[j].v;
            if(edge[j].w>0&&dis[v]            {
                mindis=dis[v];
                cur[u]=j;
            }
        }
        if((--gap[dis[u]])==0)
            break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return flow;
}
int main()
{
    int f,d;
    while(scanf("%d%d%d",&n,&f,&d)!=EOF)
    {
        int ff,dd;
        s=0;
        t=d+f+2*n+1;
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=f;i++) addedge(0,i,1);
        for(int i=1;i<=n;i++) addedge(i+f,i+n+f,1);  //2*n+f
        for(int i=1;i<=d;i++) addedge(i+f+2*n,d+f+2*n+1,1);
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d%d",&ff,&dd);
            for(int j=1;j<=ff;j++)
            {
                scanf("%d",&x);
                addedge(x,i+f,1);
            }
            for(int j=1;j<=dd;j++)
            {
                scanf("%d",&x);
                addedge(i+n+f,x+f+2*n,1);
            }
        }
        n=d+f+2*n+2;
        printf("%d/n",sap());
    }
    return 0;
}