首页 > 代码库 > poj1149 PIGS --- 最大流EK
poj1149 PIGS --- 最大流EK
有m个猪圈,给出初始时每个猪圈里有几头猪,有n个顾客,每个顾客可能在某k个猪圈里买猪,总共要买a头。
顾客依次买猪,每次买完后,猪圈主人可以把猪圈里的猪转移到别的猪圈。每个猪圈的容量是无限大的。
问一天最多能卖多少猪。
整体读下来可以知道,要卖更多的猪,就要在每个顾客买之前,把尽量多的猪转移到下一个顾客要可以买的k个猪圈里。
也就是一个最大流问题。
把相邻两个顾客所选的猪圈之间建边,容量是inf。
添加一个源点与第一个顾客建边,权值为每个猪圈里猪的头数,第一次的容量是受猪圈里猪的数量限制的而不是无限大。
每个顾客和汇点建边,权值是顾客要购买的数量,最大流是在所有顾客购买能力范围内的。
注释的代码是0ms的。
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #define eps 1e-6 #define ll __int64 const int maxn=105; using namespace std; int m,n,s,t; int c[105][105],f[105][105],minflow[105],pre[105],pig[1005],last[1005]; int p[maxn]; /*void ford() { int q[105],qs,qe; int v,p,i,j; memset(f,0,sizeof f); minflow[0]=inf; while(1) { for(i=0;i<104;i++) pre[i]=-2; pre[0]=-1; qs=0;qe=1; q[qs]=0; while(qs<qe&&pre[t]==-2) { v=q[qs++]; for(i=0;i<t+1;i++) { if(pre[i]==-2&&(p=c[v][i]-f[v][i])) { pre[i]=v; q[qe++]=i; minflow[i]=minflow[v]<p?minflow[v]:p; } } } if(pre[t]==-2) break; for(i=pre[t],j=t;i!=-1;j=i,i=pre[i]) { f[i][j]+=minflow[t]; f[j][i]=-f[i][j]; } } for(i=0,p=0;i<t;i++) p+=f[i][t]; printf("%d\n",p); }*/ bool bfs() { queue<int> q; bool vis[maxn]; memset(vis,0,sizeof vis); memset(p,-1,sizeof p); q.push(s); vis[s]=1; while(!q.empty()) { int e=q.front(); if(e==t) return 1; q.pop(); for(int i=0;i<=n+1;i++)//注意点的范围 { if(c[e][i]&&!vis[i]) { vis[i]=1; p[i]=e; q.push(i); } } } return 0; } int ek() { int u,ans=0,mn; while(bfs()) { mn=inf; u=t; while(p[u]!=-1) { mn=min(mn,c[p[u]][u]); u=p[u]; } ans+=mn; u=t; while(p[u]!=-1) { c[p[u]][u]-=mn; c[u][p[u]]+=mn; u=p[u]; } } return ans; } int main() { int i,k,a,m; while(~scanf("%d%d",&m,&n)) { for(i=1;i<=m;i++) scanf("%d",&pig[i]); s=0,t=n+1; memset(c,0,sizeof c); memset(last,0,sizeof last); for(i=1;i<=n;i++) { scanf("%d",&k); while(k--) { scanf("%d",&a); if(last[a]==0) c[s][i]+=pig[a]; else c[last[a]][i]=inf; last[a]=i; } scanf("%d",&c[i][t]); } // ford(); printf("%d\n",ek()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。