首页 > 代码库 > POJ 3281 Dining
POJ 3281 Dining
传送门:https://vjudge.net/problem/POJ-3281
题目大意:
这儿的主人公是N头牛,和一个农场主。每头牛都有一个特别的食谱,这是他们喜欢吃的食物和饮料。农场主准备了F种食物,和D种饮料。他想要尽可能多的牛都能都的到自己喜欢吃的食物和饮料(注每头牛只需要一份食物和一份饮料)。问这样的牛最少数量是多少。
解题思路:
这是一个最大流的题。我门可以建立如下的图。
哈哈上面的是错误的。
具体为什么,自己想一下就知道了,主要是在建图的时候有一点麻烦。
实现代码:
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cstdlib> #include <cstring> #include <queue> using namespace std; const int MAXN=5000; const int INF=1<<30; int N,F,D; struct Edge{ int to,next; int cap; Edge(int to,int next,int cap):to(to),next(next),cap(cap){}; Edge(){}; }edges[MAXN]; int head[MAXN]; int tot; void init(){ memset(head,-1,sizeof(head)); tot=0; } void addEdge(int u,int v,int cap){ edges[tot].to=v; edges[tot].cap=cap; edges[tot].next=head[u]; head[u]=tot++; } void initGraph(int s,int t){ for(int i=1;i<=F;i++){ addEdge(s,i,1); addEdge(i,s,0); } for(int i=1;i<=N;i++){ addEdge(F+i,F+N+i,1); addEdge(F+N+i,F+i,0); } for(int i=1;i<=D;i++){ addEdge(F+2*N+i,t,1); addEdge(t,F+2*N+i,0); } } int level[MAXN]; bool makelevel(int s,int t){ //cout<<"-----------"<<endl; memset(level,0,sizeof(level)); level[s]=1; queue<int>q; q.push(s); while(!q.empty()){ int u=q.front();q.pop(); if(u==t) return true; for(int i=head[u];i!=-1;i=edges[i].next){ int v=edges[i].to; if(!level[v]&&edges[i].cap){ level[v]=level[u]+1; q.push(v); } } } return false; } int dfs(int now,int maxf,int t){ if(now==t) return maxf; int ret=0,f; for(int i=head[now];i!=-1;i=edges[i].next){ int v=edges[i].to; if(edges[i].cap&&level[v]==level[now]+1){ f=dfs(v,min(maxf-ret,edges[i].cap),t); edges[i].cap-=f; edges[i^1].cap+=f; ret+=f; } if(ret==maxf) return ret; } return ret; } int Dinic(int s,int t){ int ans=0; while(makelevel(s,t)) ans+=dfs(s,INF,t); return ans; } int main(){ scanf("%d%d%d",&N,&F,&D); init(); initGraph(0,F+N+N+D+1); for(int i=1;i<=N;i++){ int CF,CD; scanf("%d%d",&CF,&CD); for(int j=0;j<CF;j++){ int TF; scanf("%d",&TF); addEdge(TF,F+i,1); addEdge(F+i,TF,0); } for(int j=0;j<CD;j++){ int TD; scanf("%d",&TD); addEdge(F+N+i,TD+F+N+N,1); addEdge(TD+F+N+N,F+N+i,0); } } /*cout<<endl; for(int i=0;i<=F+N+N+D+1;i++){ cout<<i<<" "; for(int j=head[i];j!=-1;j=edges[j].next) cout<<edges[j].to<<"("<<edges[j].cap<<") "; cout<<endl; }*/ cout<<Dinic(0,F+N+N+D+1)<<endl; return 0; }
POJ 3281 Dining
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。