Description
An example is in figure 1. The label x/y of power station u shows that p(u)=x and p max(u)=y. The label x/y of consumer u shows that c(u)=x and c max(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6.
Input
Output
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7
(3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5
(0)5 (1)2 (3)2 (4)1 (5)4
Sample Output
15
6
Hint
思路:刚开始不理解EK算法中正向与反向边中的加减,所以查找了好多资料,有了前一篇博客的转载才理解其中的意思,所以才完成了这道题,可以说搞了一天了,哎呀,刚才又因为输入的问题卡了好久,晕死……
因为所以的电站都是源点,所有的消费者都是汇点,所以新建一个源点把所有的电站连起来,再新建一个汇点把所有的消费者连起来就行了,我把有的点加1,就是1到n,然后0点为源点,n+1点为汇点,用EK算法就可以算出来了。
EK算法是比较简单的最大流算法,比较好理解,代码比较少。现在一步一步学习最大流算法,今天学习了最大流的所有算法,都理解了其中的意味,不过还没有敲代码,有时间再一个一个算法的敲了。
EK算法中,正向减去,因为流题加上就相当于容量减去,其差是一样的,所以可以直接把容量减去就行了。但是为何其反向边要加上呢,因为如果没有反向边的话,增广路是不能回退的,即可能还存在别的增广路使最大流更加大。比如:1,2,3,4结点之间容量都是1,若1,2,3,4是增广路,然后就不存在增广路了,则最大流为1;但是这个最大流是错的,因为可以过1,2,4这条增广路以及1,3,4这条增广路使得最大流为2.如果加入反向边,那么寻找第一次增广路即1,2,3,4的时候,反向边(3,2)加了一个数,那么就不为0,此时最大流为1;则可以寻找到第二条增广路1,3,2,4,此时最大流为2正确…………(详细的在前一篇博客中有转载的详解)
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define MM 10002
#define MN 105
#define INF 168430090
using namespace std;
typedef long long ll;
int n,m,k,t,ans,pre[MN],vis[MN],Map[MN][MN];
int bfs()
{
mem(vis,0); queue<int>q; q.push(0); vis[0]=1;
while(!q.empty()) //找增广路
{
int u=q.front(); q.pop();
for(int v=0;v<=n+1;v++)
{
if(!vis[v]&&Map[u][v])
{
pre[v]=u; //记录前向结点
if(v==n+1) return 1;
q.push(v); vis[v] = 1;
}
}
}
return 0;
}
void change()
{
int i,sum=INF;
for(i=n+1; i != 0; i = pre[i])
sum = min(sum,Map[pre[i]][i]);
for(i=n+1; i != 0; i = pre[i])
{
Map[pre[i]][i]-=sum; //正向边减
Map[i][pre[i]]+=sum; //反向边加
}
ans+=sum;
}
int main()
{
while(~scanf("%d%d%d%d",&n,&m,&k,&t))
{
mem(Map,0); ans=0;
int u,v,w;
while(t--)
{
while(getchar()!='(');
scanf("%d,%d)%d",&u,&v,&w);
Map[u+1][v+1]+=w;
}
while(m--)
{
while(getchar()!='(');
scanf("%d)%d",&u,&w);
Map[0][u+1]=w; //新建源点0
}
while(k--)
{
while(getchar()!='(');
scanf("%d)%d",&u,&w);
Map[u+1][n+1]=w; //新建汇点n+1
}
while(bfs()) change();
pri(ans);
}
return 0;
}