poj 3281 Dining （最大流）

思路：將牛拆開，分別一一對應，然後構建有向圖： S(源點)    食物（1-F） 牛（1——N） 牛（1-N） 飲料（1-D） 匯點T 單向邊，每條邊容量為1 ，轉換為最大流問題： 至於為什麼要把對應的牛拆成兩個頂點：保證一條牛不會被分配多組食物和飲料 代碼：

#include<iostream>  
#include<queue>  
#include<cstring>  
using namespace std;  
const int MAXN=101;  
bool likeF[MAXN][MAXN];  //食物的喜好   
bool likeD[MAXN][MAXN];  
const int MAXV=MAXN*4+2;  
int c[MAXV][MAXV],N,F,D; //c:鄰接矩陣   
bool visited[MAXV];  
int pre[MAXV];  
  
bool bfs(int s,int t)  
{  
    memset(visited,0,sizeof(visited));  
    queue<int> que;  
    que.push(s);  
    visited[s]=1;  
    while(!que.empty())  
    {  
        int p=que.front();  
        que.pop();  
        for(int i=0;i<=t;i++)  
        {  
            if( !visited[i]&& c[p][i]>0){  
                que.push(i);  
                visited[i]=1;  
                pre[i]=p;  
                if(i==t) return 1;  
            }  
        }  
    }  
    return 0;  
}  
  
int ek(int s,int t)  
{  
    int max_flow=0;  
    while(1)  
    {  
        if(!bfs(s,t)) break;  
        int i=t;  
        while(i!=s)  
        {  
            c[pre[i]][i]-=1;  
            c[i][pre[i]]+=1;  
            i=pre[i];  
        }  
        max_flow++;  
    }  
    return max_flow;  
}  
void solve()  
{  
    // 0:N-1 食物一側的牛  
    // N:2N-1 飲料一側的牛  
    // 2N:2N+F-1 食物  
    // 2N+F:2N+F+D-1 飲料  
    // 構建圖模型   
      
      
    int s=N*2+F+D,t=s+1;  
    for(int i=0;i<F;i++){ //s與食物之間連邊   
        c[s][2*N+i]=1;  
    }   
    for(int i=0;i<D;i++){ //飲料和t之間連邊   
        c[2*N+F+i][t]=1;  
    }   
    for(int i=0;i<N;i++){  
        c[i][i+N]=1;  
        for(int j=0;j<F;j++){  
            if(likeF[i][j]) c[2*N+j][i]=1;  
        }  
        for(int j=0;j<D;j++){  
            if(likeD[i][j]) c[i+N][j+2*N+F]=1;  
        }  
    }   
    cout<<ek(s,t)<<endl;  
}  
int main()  
{  
    while(cin>>N>>F>>D)  
    {  
        memset(likeD,0,sizeof(likeD));  
        memset(likeF,0,sizeof(likeF));  
              
        for(int i=0;i<N;i++){  
            int fn,dn;  
            cin>>fn>>dn;  
            for(int j=0;j<fn;j++) {  
                int f;  
                cin>>f;  
                likeF[i][f-1]=1;  
            }  
            for(int j=0;j<dn;j++){  
                int d;  
                cin>>d;  
                likeD[i][d-1]=1;  
            }  
        }  
        memset(c,0,sizeof(c));  
        solve();  
    }  
    return 0;  
}