本文主要是介绍poj1149 - PIGS（最大流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
地址：点击打开链接
题意：有 M 个猪圈，每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依 次来了 N 个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪。每 个顾客分别都有他能够买的数量的上限。每个顾客走后，他打开的那些猪圈中的 猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。问总共 最多能卖出多少头猪。（1 <= N <= 100, 1 <= M <= 1000）
举个例子来说。有 3 个猪圈，初始时分别有 3、 1 和 10 头猪。依次来了 3 个顾客， 第一个打开 1 号和 2 号猪圈，最多买 2 头；第二个打开 1 号和 3 号猪圈，最多买 3 头；第三个打开 2 号猪圈，最多买 6 头。那么，最好的可能性之一就是第一个 顾客从 1 号圈买 2 头，然后把 1 号圈剩下的 1 头放到 2 号圈；第二个顾客从 3 号圈买 3 头；第三个顾客从 2 号圈买 2 头。总共卖出 2+3+2=7 头。
思路：
• 每个顾客分别用一个结点来表示。
• 对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的 猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一 条，容量相加。
• 对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i∈[1, n)，从该 猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为∞。
• 从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。
建图合并：
规律 1. 如果几个结点的流量的来源完全相同，则可以把它们合并成一个。
规律 2. 如果几个结点的流量的去向完全相同，则可以把它们合并成一个。
规律 3. 如果从点 u 到点 v 有一条容量为∞的边，并且点 v 除了点 u 以外没 有别的流量来源，则可以把这两个结点合并成一个。
总结：
在面对网络流问题时，如果一时想不出很好的构图方法，不如先构造一个最 直观，或者说最“硬来”的模型，然后再用合并结点和边的方法来简化这个模 型。经过简化以后，好的构图思路自然就会涌现出来了。这是解决网络流问题 的一个好方法。
代码：
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXM 1005
#define MAXV 105
#define INF 0x7f7f7f7f
using namespace std; int res[MAXV][MAXV]; //cap为最大容量,f为流量
int dis[MAXV]; //表示多少层
int n,source,sink,maxflow; //s为源点,t为汇点
int min(int a,int b){return a > b ? b : a;} int bfs(){ //找路 int k; queue<int> q; memset(dis,-1,sizeof(dis)); //层数 dis[sink]=0; q.push(sink); while(!q.empty()){ k=q.front(); q.pop(); for(int i = 0; i <=n+1; i++){ if(dis[i]==-1 && res[i][k]){ dis[i] = dis[k] + 1; q.push(i); } } if(k==source) return 1; } return 0;
} int dfs(int cur,int cp){ if(cur==sink) return cp; int tmp=cp,t;for(int i=0; i<=n+1 && tmp;i++){if(dis[i]+1==dis[cur] && res[cur][i]){ t=dfs(i,min(res[cur][i],tmp)); res[cur][i]-=t; res[i][cur]+=t; tmp-=t; } } return cp-tmp;
} void dinic(){ maxflow=0; while(bfs()){ maxflow+=dfs(source,INF); }
} int main(){ int i,m,cnt,num,j; int pig[MAXM]; int k[MAXM]; while(~scanf("%d%d",&m,&n)){ memset(k,0,sizeof(k)); memset(res,0,sizeof(res)); for(i=1;i<=m;i++) scanf("%d",&pig[i]); //建图---------------------------------- source=0,sink=n+1; for(i=1;i<=n;i++){ scanf("%d",&cnt); for(j=1;j<=cnt;j++){ scanf("%d",&num); if(!k[num]) res[source][i]+=pig[num]; //第一个打开的客户建立到s的路 else res[k[num]][i]=INF; //对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i∈[1, n)，从该 猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为∞。 k[num]=i; } scanf("%d",&num); res[i][sink]=num; } //结束----------------------------------n=sink+1; dinic(); printf("%d\n",maxflow); } return 0;
}
这篇关于poj1149 - PIGS（最大流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
