poj3281 網絡流（拆點加源）

329ms。構圖題， 自己建源點匯點，將源點連接所有的食物，將一頭牛拆成兩個點。牛i-1，牛i-2，將食物與牛i-1連，然後所有的牛i，連接牛i-1和牛i-2，將牛i-2於飲料相連。最後將所有的飲料與匯點相連。

構圖就像這樣： 源點s-->食物F-->牛1-->牛2-->飲料D-->匯點t

將牛拆成兩個點並且放在中間就可以同時連接食物和飲料。然後牛的兩個節點之間連邊，容量為1. 食物及飲料讀數據於牛1，牛2相連。

#include<iostream>
#include<cstdio>        //EK()算法。時間復雜度（VE^2）
#include<queue>
#include<cstring>

using namespace std;
const int maxn = 500;
const int INF = 0x3fffffff;

int N,F,D;
int Fi[maxn];
int Di[maxn];

int g[maxn][maxn];
int flow[maxn],pre[maxn];
bool vis[maxn];
int n;

int bfs(int s,int e){
    memset(pre,-1,sizeof(pre));
    memset(vis,false,sizeof(vis));
    queue<int > q;
    vis[s] = true;
    for(int i=1;i<=n;i++)
        flow[i]=INF;
    q.push(s);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        if(now==n)  break;
        for(int i=1;i<=n;i++){                //尋找增廣路最小流量
            if(!vis[i]&&g[now][i]>0){
                vis[i] = true;
                flow[i] = min(flow[now],g[now][i]);
                pre[i] = now;
                q.push(i);
            }
        }
    }
    if(!vis[e]|| e==1)                         //找不到完整的增廣路or源點匯點重合
         return -1;
    else
         return flow[e];
}

int EK(int s,int e){
    int temp,d,res,maxflow;
    maxflow = 0;
    while((d=bfs(s,e))!=-1){
         maxflow += d;
         temp=n;
         while(temp!=1){
             res = pre[temp];
             g[res][temp]-=d;               //正向邊
             g[temp][res]+=d;               //反向邊
             temp = res;
         }
    }
    return maxflow;
}

int main(){
    memset(g,0,sizeof(g));
    memset(flow,0,sizeof(flow));
    cin>>N>>F>>D;
    n = 1 + F + N + N + D + 1;
    for(int i = 1; i <= F; i++)
    {
        g[1][i+1] = 1;
    }
    for(int i = 1; i<= D; i++)
    {
        g[1+F+N+N+i][n] = 1;
    }
    for(int i = 1; i <= N; i++)
    {
        g[1+F+i][1+F+N+i] = 1;
    }
    int nf,nd;
    for(int i = 1; i <= N; i++)
    {
        cin>>nf>>nd;
        int x;
        while(nf--)
        {
            cin>>x;
            g[1+x][1+F+i] = 1;
        }
        while(nd--)
        {
            cin>>x;
            g[1+F+N+i][1+F+N+N+x] = 1;
        }
    }
    cout<<EK(1,n)<<endl;
    return 0;
}