网络流之一般增广路算法标号法实现

数据输入格式：首先输入顶点个数n和弧数m，然后输入每条弧的数据。规定源点为顶点0，汇点为顶点n-1.每条弧的数据格式为：u，v，c，f，分别表示这条弧的起点，终点，容量和流量。顶点序号从0开始。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 1005 #define MAXN 1000 #define mod 1000000009 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; struct ArcType//弧结构 { int c,f;//容量，流量 }; ArcType Edge[MAXN][MAXN];//邻接矩阵（每个元素为ArcType类型） int n,m; //顶点的个数和弧数 int flag[MAXN]; //顶点状态：-1――未标号，0――已标号未检查，1――已标号已检查 int prev[MAXN]; //标号的第一个分量：指明标号是从哪里得到的，以便找到可改尽量 int alpha[MAXN]; //标号的第二个分量：可改进量 int que[MAXN]; //队列 int v; //从队列中取出来的队列头元素 int qs,qe; //队列头位置，队列尾位置 int i,j; //循环变量 void ford() { while (1) //标号直到不存在可改进路 { //标号前对顶点状态数组初始化为-1 memset(flag,-1,sizeof(flag)); memset(prev,-1,sizeof(prev)); memset(alpha,-1,sizeof(alpha)); flag[0]=0; prev[0]=0; alpha[0]=INF; //源点为已标号未检查点 qs=qe=0; que[qe]=0;//源点入队 qe++; //qs
             
              0) { flag[i]=0; prev[i]=-v; //给顶点i标号（已标号未检查） alpha[i]=min(alpha[v],Edge[i][v].f); que[qe]=i; //顶点i入队 qe++; } } } flag[v]=1; } //end of while (qs
              
               %d:%d\n",i,j,Edge[i][j].f); } } printf("maxFlow:%d\n",maxFlow); } int main() { int u,v,c,f; //弧的起点，终点，容量，流量 while (scanf("%d%d",&n,&m)!=EOF) //读入顶点个数n和弧数m { for (i=0;i

网络流 之 一般增广路算法 标号法实现