hdu 3549 Flow Problem Edmonds_Karp算法求解最大流-白红宇

hdu 3549 Flow Problem Edmonds_Karp算法求解最大流

阅读量：5256 次

发布时间：2019-06-14

本文共 2421 字，大约阅读时间需要 8 分钟。

题意:N个顶点M条边，(2 <= N <= 15, 0 <= M <= 1000)问从1到N的最大流量为多少？

分析:直接使用Edmonds_Karp算法即可；下面是对增广路的一些理解和代码的解释；

残量:容量-流量；

增广：求出从源点到汇点的一条道路中所有残量的最小值d,把对应的所有边上的流量增加d,反向边(t->s)流量减少d(反向边的cap其实一直是0，只是flow为负了);

技巧:这次的ins的标号是从0开始的，即tot++,之前我都是++tot;这样head初始化就变为-1了，不能再是0；这样是为了每条边和其反向边的编号是存在XOR关系；即每次找到一条道路后从t找回到s(所以要在边中加入from)对每条边及其反向边的残量变化；

注意:同时增广路可达到所有边数的两倍；以及每次寻找路径的时候要把queue清空，否则MLE..

Edmond_Karp算法BFS查找每次需要O(m)总时间复杂度为O(n*m²),不够快所以跑了218ms

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;#define rep0(i,l,r) for(int i = (l);i < (r);i++)#define rep1(i,l,r) for(int i = (l);i <= (r);i++)#define rep_0(i,r,l) for(int i = (r);i > (l);i--)#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)#define MS0(a) memset(a,0,sizeof(a))#define MS1(a) memset(a,-1,sizeof(a))#define inf 0x3f3f3f3f#define pb push_backtemplate
                  
                   void read1(T &m){ T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f;}template
                   
                    void read2(T &a,T &b){read1(a);read1(b);}template
                    
                     void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}template
                     
                      void out(T a){ if(a>9) out(a/10); putchar(a%10+'0');}const int M = 1000;const int N = 20;int head[M<<1],tot;struct edge{ int from,to,cap,flow,Next;}e[M<<1];void ins(int u,int v,int cap,int flow){ e[tot].Next = head[u]; e[tot].from = u;//为了t->s时由v推到u; e[tot].to = v; e[tot].cap = cap; e[tot].flow = flow; head[u] = tot++;}queue
                      
                        q;int p[N];//记录路径中边的标号int a[N];//起点到i的可改进量int Edmonds_Karp(int s,int t){ int flow = 0; for(;;){ MS0(a); while(!q.empty()) q.pop(); a[s] = inf; q.push(s); while(!q.empty()){ int u = q.front();q.pop(); for(int id = head[u];~id;id = e[id].Next){ int v = e[id].to,c = e[id].cap,f = e[id].flow; if(!a[v] && c > f){ p[v] = id; a[v] = min(a[u],c - f);// ** 递推到a[v] q.push(v); } } if(a[t]) break; } if(!a[t]) break; for(int u = t;u != s;u = e[p[u]].from){ e[p[u]].flow += a[t]; e[p[u]^1].flow -= a[t]; } flow += a[t]; } return flow;}int main(){ int n,T,kase = 1; read1(T); while(T--){ int V,E; read2(V,E); MS1(head);tot = 0; rep0(i,0,E){ int u,v,w; read3(u,v,w); ins(u,v,w,0);ins(v,u,0,0); } printf("Case %d: ",kase++); out(Edmonds_Karp(1,V)); puts(""); } return 0;}

转载于:https://www.cnblogs.com/hxer/p/5187231.html

你可能感兴趣的文章