本文主要是介绍poj（1459）Power Network，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解题思路：
多源多汇最大流问
题目给出很多都是废话，特别是符号s(u)，d(u)，Con还有那条公式都别管，混淆视听
难点在于构图
电站p(u)均为源点，用户c(u)均为汇点，中转站当普通点处理
第一个误区是例图， 结点 和 边 都有x/y（流量和容量），这个很容易使人产生矛盾（因为学习最大流问题是，只有 边 才有流量和容量。
但是不难发现，题目所给的例图中有多个源点，多个汇点，多个普通点，只有源点和汇点才标有 x/y，普通点没有标x/y，而且所给出的所有边都有x/y。 这无疑在促使我们对图做一个变形： 建议一个超级源s，一个超级汇t，使s指向所有源点，并把源点的 容量y 分别作为这些边的 容量，使所有汇点指向t，并把汇点的容量y分别作为这些边的 容量，然后本来是源点和汇点的点，全部变为普通点。这样就把“多源多汇最大流”变形为“单源单汇最大流”问题。
第二个误区就是流量值。 学习最大流问题时，会发现边上的流量值是给定初始值的，但是这题的输入只有容量，没有流量，很多人马上感觉到无从入手。其实边上的流量初始值为多少都没有所谓，解最大流需要用到的只有容量。但是一般为了方便起见， 会把所有边的流量初始化为0。这样做有一个最大的好处，就是可以回避 反向弧 的存在，这个下面详细叙述。
本题中要注意的是：
1、 如果输入中，某一点上有环，就无视掉。环是否存在不影响最终结果。
2、 一般两点之间都是单边，一旦存在双边也没有问题，因为由定义知两个方向的容量一定相等（其实不相等也无妨，因为其中有一条为 反向弧，前面已经提到 反向弧 是可以直接回避、无视的，因此反向弧上的容量为多少就不重要了），而且在寻找增广路的标号过程中，搜索的是未标号的点，就是说(u,v)这条弧即使是双向的，但一旦从u到达v后，就不能回头了，因为两者都被标记了，即另外一条弧就不起任何作用了。
下面详细说说为什么能够回避反向弧。
首先需要明确，任意一个点j上记录的信息有：
1、 寻找增光路时，除超级源s外，增广路上任一点j都有一个唯一的前驱i（i被记录在j）
2、 min{从i到j的容流差,l(vi)}
3、 构图时，除超级汇t外，图上任一点j都会直接指向一些点(这些点作为后继点，同在记录在j)
从这个特点可以知道，从超级源开始寻找增广路时，万一遇到双向边，正向弧，反向弧自动被回避。万一遇到单向边，如果是非饱和正向弧，就会继续走下去；如果是反向弧，这条弧必然是 零弧（每条边初始化流量均为0），定义知如果增广路有反向弧，它必须要是非零弧，而且由于反向弧每次都不会经过，所以在改进增广路时反向弧上的流量也不会被改变，永远为0，也就与最终结果无关了
最后当无法寻找增广路时，最大流就是与超级源s直接关联的边上的 流量之和
#include"string.h"
#include"stdio.h"
#include"queue"
#define inf 9999999
using namespace std;
int r[300][300];
int pre[300];
int visit[300];
int n,m;
int bfs(int s,int t)
{
int p,i;
queue<int>q;
memset(visit,0,sizeof(visit));
memset(pre,0,sizeof(pre));
pre[s]=s;
visit[s]=1;
q.push(s);
while(!q.empty())
{
p=q.front();
q.pop();
for(i=0;i<=n+1;i++)
{
if(visit[i]==0&&r[p][i])
{
pre[i]=p;
visit[i]=1;
if(i==t)
return 1;
q.push(i);
}
}
}
return 0;
}
int EK(int s,int t)
{
int d,i,flow=0;
while(bfs(s,t))
{
d=inf;
for(i=t;i!=s;i=pre[i])
d=d<r[pre[i]][i]?d:r[pre[i]][i];
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,a,b,c,np,nc;
while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
{
memset(r,0,sizeof(r));
for(i=0;i<m;i++)
{
scanf(" (%d,%d)%d",&a,&b,&c);
r[a+1][b+1]=c;
}
for(i=0;i<np;i++)
{
scanf(" (%d)%d",&a,&b);
r[0][a+1]=b;
}
for(i=0;i<nc;i++)
{
scanf(" (%d)%d",&a,&b);
r[a+1][n+1]=b;
}
printf("%d\n",EK(0,n+1));
}
return 0;
}
这篇关于poj（1459）Power Network的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
