本文主要是介绍poj（1149）PIGS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//此题的难点在于，如何建图。让r获得一定的值。。
//每个顾客分别用一个节点来表示。
//对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。
//对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i ∈ [1, n)，从该猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为 +∞。
//从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。
这道题目的大意是这样的：
有 M 个猪圈（M ≤ 1000），每个猪圈里初始时有若干头猪。 一开始所有猪圈都是
闭的。 依次来了 N 个顾客（N ≤ 100），每个顾客分别会打开指定的几个猪圈，
从中买若干头猪。 每个顾客分别都有他能够买的数量的上限。 每个顾客走后，他打
开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新
关上。 问总共最多能卖出多少头猪。
举个例子来说。有 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 头,不难想像，这个问题的网络模型可以很直观地构造出来。就拿上面的
例子来说可以构造出图1所示的模型（图中凡是没有标数字的边容量都是+∞）：
三个顾客，就有三轮交易，每一轮分别都有 3 个猪圈和 1 个顾客的节点。
从源点到第一轮的各个猪圈各有一条边，容量就是各个猪圈里的猪的初始数量。
从各个顾客到汇点各有一条边，容量就是各个顾客能买的数量上限。
在某一轮中，从该顾客打开的所有猪圈都有一条边连向该顾客，容量都是 +∞。
最后一轮除外，从每一轮的 i 号猪圈都有一条边连向下一轮的 i 号猪圈，容量都是 +∞，表示这一轮剩下的猪可以留到下一轮。
最后一轮除外，从每一轮被打开的所有猪圈，到下一轮的同样这些猪圈，两两之间都要连一条边，表示它们之间可以任意流通。
#include"stdio.h"
#include"string.h"
#include"queue"
#define inf 9999999999
int r[1001][101];
int visit[1001],vis[1001];
int pre[1001],h[1001];
using namespace std;
int n,m;
int bfs(int s,int t)
{
int p,i;
memset(pre,0,sizeof(pre));
memset(visit,0,sizeof(visit));
queue<int>q;
pre[s]=s;
visit[s]=1;
q.push(s);
while(!q.empty())
{
p=q.front();
q.pop();
for(i=1;i<=n+1;i++)
{
if(!visit[i]&&r[p][i])
{
visit[i]=1;
pre[i]=p;
if(i==t)
return 1;
q.push(i);
}
}
}
return 0;
}
int EK(int s,int t)
{
int flow=0,d,i;
while(bfs(s,t))
{
d=inf;
for(i=t;i!=s;i=pre[i])
d=d>r[pre[i]][i]?r[pre[i]][i]:d;
for(i=t;i!=s;i=pre[i])
{
r[pre[i]][i]-=d;
r[i][pre[i]]+=d;
}
flow+=d;
}
return flow;
}
int main()
{
int i,j,k,t,p;
while(scanf("%d%d",&m,&n)!=EOF)
{
for(i=1;i<=m;i++)
scanf("%d",&h[i]);
memset(r,0,sizeof(r));
memset(vis,0,sizeof(vis));//vis的作用除了标记，还记住了上一个开此猪圈的人。。
for(i=1;i<=n;i++)
{
scanf("%d",&k);
for(j=1;j<=k;j++)
{
scanf("%d",&t);
if(vis[t]==0)//如果是第一个人则与源点的值为该猪圈猪的头数。。
{
r[0][i]+=h[t];
vis[t]=i;
}
else//不然无穷大。
{
r[vis[t]][i]=inf;
pre[t]=i;
}
}
scanf("%d",&p);
r[i][n+1]=p;
}
printf("%d\n",EK(0,n+1));
}
return 0;
}
这篇关于poj（1149）PIGS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
