水彩莲蓬商务教育PPT模板.ppt

#include<>
#define n 6 /*固定网络中有六个顶点*/
/*该数组表现了各个顶点之间的相连关系,0表示没有连接,3表示两顶点之间的容量*/
1[n+1][n+1]={{0,0,0,0,0,0,0},
{0,0,5,4,0,0,0},
{0,0,0,0,4,0,0},
{0,0,3,0,0,3,0},
{0,0,0,0,0,1,2},
{0,0,0,0,0,0,8},
{0,0,0,0,0,0,0}}; /*正向边矩阵,非0值亦代表容量*/
2[n+1][n+1]={{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,-5,0,-3,0,0,0},
{0,-4,0,0,0,0,0},
{0,0,-4,0,0,0,0},
{0,0,0,-3,-1,0,0},
{0,0,0,0,-2,-8,0}};/*负向边矩阵*/
/*该数组用来纪录各个顶点之间的流量,初始流量为0*/
int flow[n+1][n+1]={{-1,-1,-1,-1,-1,-1,-1},
{-1,0,0,0,0,0,0},
{-1,0,0,0,0,0,0},
{-1,0,0,0,0,0,0},
{-1,0,0,0,0,0,0},
{-1,0,0,0,0,0,0},
{-1,0,0,0,0,0,0}};
struct flags{
int p;/*前驱点的标号,若p=0表示该顶点没有被标号*/
int d;/*direction,d=1表示正向,d=-1表示负向*/
int c;/*检查标识,c-1检查过,c=0未检查*/
int a;/*增流量*/
}flag[n+1];
/*以上数组均只用[1]到[6]中的数值*/
int add=0;/*增流标记*/
int end=0; /*算法结束标记*/
main()
{
int i=0;
int maxflow=0;
clrscr();
while(end!=1)
{
sign();
if(add==1)
addflow();
}
/*输出最大流*/
for(i=1;i<=n;i++)
{
maxflow+=flow[1][i];
}
printf("The maxflow is:%d",maxflow);
getch();
}
sign() /*标号函数*/
{
int i=0;
register int j=0;
int js=0;
int check=0;/*与i相邻接的顶点是都已被标号则check=1*/
flag[1].p=-1;
flag[1].d=1;
flag[1].c=0;
flag[1].a=32767; /*初始化源点*/
for(js=1;js<=100;js++) /*强制循环100次,认为算法总能在有限次内得出正确结果*/
{
for(i=1;i<=n;i++)
{
if(flag[i].p!=0&&flag[i].c==0) /*找出已标号但未检查的顶点j*/
{
for(j=1;j<=n;j++)/*找与i向邻