首页 > 代码库 > POJ1149 PIGS【特殊建图,最大流】
POJ1149 PIGS【特殊建图,最大流】
看题解做的,看懂了怎么建图后,套上挑战icpc的最大流模版,就A了,上题解
题意:M个猪圈,N个顾客,每个顾客有一些的猪圈的钥匙,只能购买这些有钥匙的猪圈里的猪,而且要买一定数量的猪,每个猪圈有已知数量的猪,
但是猪圈可以重新打开,将猪的个数,重新分配,以达到卖出的猪的数量最多。
思路:刚学网络流,表示很菜很菜很菜~~
①构造网络,将顾客看成源点和汇点以外的结点,并设另外两个节点:源点和汇点。
②源点和每个猪圈的第一个顾客连边,边的权是开始时候猪圈中猪的数量。
③ 若源点和某个节点之间有重边,则将权合并
④顾客j紧跟顾客i之后打开某个猪圈,则<i.j>的权是正无穷。
⑤每个顾客和会点之间连边,边的权值是顾客所希望购买的猪的数量。
例如:样例中的就可以建立如图:
其中inf是正无穷~~
#include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <vector> using namespace std; const int MAXN=1111; const int MAX_V=1111; const int INF=(1<<31)-1; int pignum[MAXN]; int pigwant[MAXN]; int first[MAXN];//first[i]代表第i个猪圈第一个进去的是谁 int enterloop[MAXN][MAXN]; bool getthrough[MAXN][MAXN]; int n,m; struct edge{int to,cap,rev;}; vector<edge>G[MAX_V]; bool used[MAX_V]; void add_edge(int from,int to,int cap) { G[from].push_back((edge){to,cap,G[to].size()}); G[to].push_back((edge){from,0,G[from].size()-1}); } int dfs(int v,int t, int f) { if(v==t) return f; used[v]=true; for(int i=0;i<G[v].size();i++) { edge& e=G[v][i]; if(!used[e.to]&&e.cap>0) { int d=dfs(e.to,t,min(f,e.cap)); if(d>0) { e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t) { int flow=0; while(true) { memset(used,0,sizeof(used)); int f=dfs(s,t,INF); if(f==0) return flow; flow+=f; } } void make_map() { int start=0; int end=m+1; for(int i=1;i<=n;i++) { add_edge(start,first[i],pignum[i]); } for(int i=1;i<=n;i++) { for(int j=1;j<enterloop[i][0];j++) { if(!getthrough[enterloop[i][j]][enterloop[i][j+1]]) { add_edge(enterloop[i][j],enterloop[i][j+1],INF); getthrough[enterloop[i][j]][enterloop[i][j+1]]=true; } } } for(int i=1;i<=m;i++) { add_edge(i,end,pigwant[i]); } } int main() { #ifndef ONLINE_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif scanf("%d%d",&n,&m);//n个猪圈,m个人 for(int i=1;i<=n;i++) scanf("%d",&pignum[i]); for(int i=1;i<=m;i++)//第i个顾客 { int loopnum,wantpig; scanf("%d",&loopnum); for(int j=1;j<=loopnum;j++)//第i个顾客去的几个猪圈,要是还没人去,他就是第一个去的 { int loopindex;scanf("%d",&loopindex); enterloop[loopindex][++enterloop[loopindex][0]]=i; if(first[loopindex]==0) first[loopindex]=i; } scanf("%d",&pigwant[i]);//第i个顾客想要几头猪 } make_map(); int ans=max_flow(0,m+1); printf("%d\n",ans); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。