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

时间：2023-11-28 11:44:26

Flow Problem

题意: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*m2),不够快所以跑了218ms

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

#include<stack>

#include<set>

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_back

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

template<typename T>

void out(T a)

{

    if(a>) out(a/);

    putchar(a%+'');

}

const int M = ;

const int N = ;

int head[M<<],tot;

struct edge{

    int from,to,cap,flow,Next;

}e[M<<];

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<int> q;

int p[N];//记录路径中边的标号

int a[N];//起点到i的可改进量

int Edmonds_Karp(int s,int t)

{

    int flow = ;

    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]^].flow -= a[t];

        }

        flow += a[t];

    }

    return flow;

}

int main()

{

    int n,T,kase = ;

    read1(T);

    while(T--){

        int V,E;

        read2(V,E);

        MS1(head);tot = ;

        rep0(i,,E){

            int u,v,w;

            read3(u,v,w);

            ins(u,v,w,);ins(v,u,,);

        }

        printf("Case %d: ",kase++);

        out(Edmonds_Karp(,V));

        puts("");

    }

    return ;

}

相关文章