poj 3281 Dining (最大流)

发布时间:2017-1-20 15:44:55 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 3281 Dining (最大流)",主要涉及到poj 3281 Dining (最大流)方面的内容,对于poj 3281 Dining (最大流)感兴趣的同学可以参考一下。

题目;http://poj.org/problem?id=3281 思路:将牛拆开,分别一一对应,然后构建有向图: 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; }

上一篇:POJ March of the Penguins
下一篇:两种删除去重复记录的sql写法

相关文章

相关评论