USACO 奶牛食品(網絡流)

題目大意：

FJ的奶牛們隻吃各自喜歡的一些特定的食物和飲料，除此之外的其他食物和飲料一概不吃。某天FJ為奶牛們精心準備了一頓美妙的飯食，但在之前忘記檢查奶牛們的菜單，這樣顯然是不能不能滿足所有奶牛的要求。但是FJ又不願意為此重新來做，是以他他還是想讓盡可能多的牛吃到他們喜歡的食品和飲料。

FJ提供了F （編号為1、2、…、F）種食品并準備了D （編号為1、2、…、D）種飲料， 他的N頭牛（編号為1、2、…、N）都已決定了是否願意吃某種食物和喝某種飲料。FJ想給每一頭牛一種食品和一種飲料，使得盡可能多的牛得到喜歡的食物和飲料。

每一種食物和飲料隻能由一頭牛來用。例如如果食物2被一頭牛吃掉了，沒有别的牛能吃到食物2。

(原諒我找不到原題，隻有把學校OJ的題粘過來)

思路：網絡流的模闆題，f作為左邊一部，把每頭奶牛拆點，同一頭奶牛之間連一條邊權值為1的邊，代表這頭奶牛隻能用一次，如果不拆點，那麼同一頭奶牛就可能同時滿足兩種飲料和兩種食物，不符合題意(之前沒有拆點，結果在學校OJ的破資料下居然過了QAQ)；d作為右邊一部，起點向f部連邊，d部向終點連邊。

#include<cstdio>
#define MAXN 510
#define Min(a,b) a<b?a:b
#define INF 999999999
#define BIG 123456789
using namespace std;
int c[MAXN][MAXN];
int dd[MAXN];
int vd[MAXN];
int s,t,n,f,d,flow;
int aug(int u,int augco)
{
    int j,augc = augco,mind = t-1,delta;
    if(u == t) return augco;
    for(j = 0; j <= t; j++)
    if(c[u][j])
    {
        if(dd[u] == dd[j]+1)
        {
            delta = Min(c[u][j],augc);
            delta = aug(j,delta);
            c[u][j] -= delta;
            c[j][u] += delta;
            augc -= delta;
            if(dd[s] > t) return augco - augc;
            if(augc == 0) break;
        }
        mind = Min(mind,dd[j]);
    }
    if(augco == augc)
    {
        vd[dd[u]]--;
        if(vd[dd[u]] == 0) dd[s] = t;
        dd[u] = mind+1;
        vd[dd[u]]++;
    }
    return augco - augc;
}
void sap()
{
    vd[0] = t;
    while(dd[1] < t)
        flow += aug(1,BIG);
}
int main()
{
    int p1,p2,v;
    scanf("%d%d%d",&n,&f,&d);
	t = n*2+f+d+2;
	for(int i = 1; i <= n; i++)
		c[f+1+2*(i-1)+1][f+1+i*2] = 1;
	for(int i = 1; i <= f; i++)
		c[1][i+1] = 1;
	for(int i = 1; i <= d; i++)
		c[f+1+2*n+i][t] = 1;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d",&p1,&p2);
        for(int j = 1; j <= p1; j++)
        {   
            scanf("%d",&v);
            c[v+1][f+1+2*(i-1)+1] = 1;
        }   
        for(int j = 1; j <= p2; j++)
        {
            scanf("%d",&v);
            c[f+1+2*i][v+f+1+2*n] = 1;
        }
    }
    sap();
    printf("%d\n",flow);
}