已经好几天没写解题报告了,今天年初一,呵呵,写一个,为今年开个好头。下面步入正题:
POJ1459这道题目的要求是求最大的消耗量。我们添加一个源点s和一个汇点t,与s相连的是所有的np(生产点),边权值为其自己能产生的数值;与t相连的是所有的nc(消耗点),边权值为其消耗最大值。至此便完成了网络的构图。然后直接套用最大流的算法模版即可解决。我使用的是EK算法。
什么是EK算法?EK算法的原理是利用BFS或者DFS每次找到网络中的一条增广路径,然后修改其流量值,直至无法找到增广路径为止。
下面给出EK的源代码:
#include <iostream>
#include <memory.h>
#include <stdio.h>
#define max 65535
using namespace std;
int s,t,n,np,nc,m,tot;
int pre[102],d[102],fx[102],f[102][102],c[102][102];
char str[50];
bool visit[102];
void init()
{
int i,x,y,z;
memset(f,0,sizeof(f));//f数组表示网络边的流量
memset(c,0,sizeof(c));//c数组表示网络边的容量
s=n;
t=n+1;
n+=2;
for(i=1;i<=m;i++)
{
scanf("%s",&str);
sscanf(str,"(%d,%d)%d",&x,&y,&z);
c[x][y]=z;
}
for(i=1;i<=np;i++)
{
scanf("%s",&str);
sscanf(str,"(%d)%d",&x,&z);
c[s][x]=z;
}
for(i=1;i<=nc;i++)
{
scanf("%s",&str);
sscanf(str,"(%d)%d",&x,&z);
c[x][t]=z;
}
tot=0;
}
bool bfs()
{
int i,j,head,tail,delta,x,temp,dir,y;
head=tail=0;
memset(d,0,sizeof(d));//队列d
memset(visit,false,sizeof(visit));//访问标记
memset(fx,0,sizeof(fx));//记录边的方向,若是前向边则fx[i]=1,若是逆向边fx[i]=-1
for(i=0;i<=n;i++)//pre表示节点的前缀
pre[i]=-1;
d[head]=s;
visit[s]=true;
while(head<=tail)
{
x=d[head];
for(i=0;i<=n;i++)
if(!visit[i])
{
temp=0;
dir=0;
if(c[x][i]-f[x][i]>0)
{
temp=c[x][i]-f[x][i];
dir=1;
}
if(f[i][x]>0&&f[i][x]>temp)
{
temp=f[i][x];
dir=-1;
}
if(temp>0)
{
pre[i]=x;
fx[i]=dir;
tail++;
d[tail]=i;
visit[i]=true;
if(i==t)
{
j=t;
delta=max;
while(pre[j]!=-1)//计算delta
{
y=pre[j];
if(fx[j]==1)
delta=min(delta,c[y][j]-f[y][j]);
else
delta=min(delta,f[j][y]);
j=y;
}
j=t;
while(pre[j]!=-1)//修改流量值
{
y=pre[j];
if(fx[j]==1)
f[y][j]+=delta;
else
f[j][y]-=delta;
j=y;
}
tot+=delta;
return true;
}
}
}
head++;
}
return false;
}
void deal()
{
bool flag;
flag=bfs();
while(flag)
flag=bfs();
}
int main()
{
while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
{
init();
deal();
cout<<tot<<endl;
}
return 0;
}
除EK算法外,最大流还有更好的实现方法,如SAP,DINIC,预留推进算法。。都是些很不错的算法。
最大流是网络流的基础,一定要牢牢掌握,而最大流的根本是增光路径定理和最大流最小割定理,所以一定要理解好这两个理论基础。