poj 3281 Dining （最大流） - c++编程基础

思路：将牛拆开，分别一一对应，然后构建有向图：

S(源点) 食物（1-F）牛（1——N）牛（1-N）饮料（1-D）汇点T

单向边，每条边容量为1 ，转换为最大流问题：

至于为什么要把对应的牛拆成两个顶点：保证一条牛不会被分配多组食物和饮料

代码：

#include  
#include  
#include  
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 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>N>>F>>D)  
    {  
        memset(likeD,0,sizeof(likeD));  
        memset(likeF,0,sizeof(likeF));  
              
        for(int i=0;i>fn>>dn;  
            for(int j=0;j>f;  
                likeF[i][f-1]=1;  
            }  
            for(int j=0;j>d;  
                likeD[i][d-1]=1;  
            }  
        }  
        memset(c,0,sizeof(c));  
        solve();  
    }  
    return 0;  
}