网络上好像没有这个算法的实现
/*find函数里的就是bfs的过程,这个程序是我今天刚完成的,可能有错误,但是我测试了一下并没有错误*/
#include <stdio.h>
#include <string.h>
#include <limits.h>
const SIZE=20;
struct node {
int father,index;
};
struct queue {
int head,tail;
node n[SIZE];
};
struct ARC {
int cap,now;
};
struct graph {
ARC arc[SIZE][SIZE];
int ArcNum;
int src,dest;
int max;
void init();
int find(int &min);
int maxflow();
};
void graph::init()
{
scanf("%d",&ArcNum);
int i,j,k,c;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
arc[i][j].cap=arc[i][j].now=0;
for(k=0;k<ArcNum;k++)
{
scanf("%d %d %d",&i,&j,&c);
arc[i][j].cap=c;
}
max=0;
}
int graph::find(int &min)
{
int visited[SIZE],i,j;
queue q;
q.head=q.tail=-1;
q.tail++;
q.n[q.tail].index=src;
q.n[q.tail].father=0;
memset(visited,0,sizeof(visited));
visited[src]=1;
while(q.head < q.tail && q.tail<SIZE)
{
int j=q.n[++q.head].index;
for(i=1;i<SIZE;i++)
{
if(arc[j][i].cap && (arc[j][i].cap-arc[j][i].now) && !visited[i] && i!=dest)
{
visited[i]=1;
q.tail++;
q.n[q.tail].father=q.head;
q.n[q.tail].index=i;
}
else if(arc[j][i].cap && (arc[j][i].cap-arc[j][i].now) && !visited[i] && i==dest)
{
visited[i]=1;
q.tail++;
q.n[q.tail].father=q.head;
q.n[q.tail].index=i;
int k=q.tail,kf=q.n[k].father,f=q.n[kf].index,c=q.n[k].index;
min=INT_MAX;
while(c!=src)
{
if(arc[f][c].cap-arc[f][c].now < min)
min=arc[f][c].cap-arc[f][c].now;
c=f;
kf=q.n[kf].father;
f=q.n[kf].index;
}
f=q.tail;
c=q.n[f].index;
if(min>0)
{
max+=min;
while(f)
{
arc[f][c].now+=min;
f=q.n[f].father;
c=q.n[f].index;
}
return 1;
}
else
return 0;
}
}
}
}
int graph::maxflow()
{
scanf("%d %d",&src,&dest);
int min,i;
for(i=0;i<10;i++)
if(find(min) && min>=0)
continue;
else if(min<=0)
break;
return max;
}
int main()
{
graph g;
g.init();
printf("%d\n",g.maxflow());
return 0;
}
/*
测试数据:
input:
11
1 2 6
1 3 9
1 4 5
2 5 4
3 5 5
3 6 4
4 6 4
5 6 4
5 7 15
6 2 6
6 7 6
1 7
output:15
*/