poj 3281 Dining (最大流Dinic)

題目鏈接: poj 3281

題目大意: 有N頭奶牛，A種食物和B種飲料，每頭奶牛都有自己喜歡的食物和飲料

問有最多有多少頭奶牛既可以得到自己喜歡的食物又可以得到喜歡的飲料

解題思路: 開始沒有把奶牛分成兩個點，這樣會導致幾種食物流入同一頭奶牛

正確的構圖:

1.建立超級源點，源點分別指向A種不同的食物，容量為1

2.建立超級匯點，B種不同的飲料分別指向匯點，容量為1

3.每頭奶牛分成兩個點T和T''，T指向T''，容量為1

4.把T奶牛喜歡的食物指向T，容量為1，再把T''指向喜歡的飲料

PS:用鄰接表時要注意反向邊也要加入，因為需要不斷增廣直到最優解

代碼:

//19:37--->20:53
#include 
#include 
#include 
#define MAX 105
#define INF 0x3f3f3f3f
int S,E,visit[MAX<<2],flag[MAX<<2][MAX<<2],Map[MAX<<2][MAX<<2];
struct snode{
    int c,to,next;
}Edge[MAX*MAX*MAX];

int listb[MAX*MAX*MAX],pre[MAX<<2],Index;

int Min(int a,int b)
{
    return(a