网络流 ek

hdu3549 求最大流果题

ek算法 先bfs出一条流 然后通过不断地添加增广路 得到最大流（证明在算法书上都有）

增加了一个流 就加反向边 允许程序通过走方向边的方式进行“回滚”

i^1 = i+1(i为奇数）， i^1 = i-1（i为偶数）这样偶数位置放正边 奇数位置放反边 就可以快速找到边的逆边

pre记录路径 具体是pre存到达当前点的边的序号

pre还顺便可以记录点的访问情况 省去了一个vis数组

每次bfs找到增广路径之后 从终点找到起点 找出最小的边权 就是这次增广增加的流

这个思路是ff方法 用bfs找增广路就是ek算法

O(VE^2) 多半歇逼

就这些

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int maxn = , maxm = , inf = 0x3f3f3f3f;

struct edge{

    int u, v, w, nxt;

    edge(){}

    edge(int u, int v, int w, int nxt):u(u), v(v), w(w), nxt(nxt){}

}e[*maxm];

int cur, head[maxn], pre[maxn];

void addedge(int u, int v, int w){

    e[cur] = edge(u, v, w, head[u]);

    head[u] = cur++;

    e[cur] = edge(v, u, , head[v]);

    head[v] = cur++;

}

void init(){

    cur = ;

    memset(head, -, sizeof(head));

}

bool bfs(int st, int ed){

    queue<int>Q;

    memset(pre, -, sizeof(pre));

    Q.push(st);

    while(!Q.empty()){

        int u = Q.front();

        Q.pop();

        if(u == ed)

            return true;

        for(int i = head[u]; ~i; i = e[i].nxt){

            int v = e[i].v, w = e[i].w;

            if(w && pre[v] == -){

                pre[v] = i;

                Q.push(v);

            }

        }

    }

    return false;

}

int ek(int st, int ed){

    int ans = ;

    while(bfs(st, ed)){

        int tmp = ed, det = inf;

        while(tmp != st){

            int edges = pre[tmp];

            det = min(det, e[edges].w);

            tmp = e[edges].u;

        }

        tmp = ed;

        while(tmp != st){

            int edges = pre[tmp];

            e[edges].w -= det;

            e[edges^].w += det;

            tmp = e[edges].u;

        }

        ans += det;

    }

    return ans;

}

int main(){

    int t, kase = ;

    scanf("%d", &t);

    while(t--){

        init();

        int n, m;

        scanf("%d%d", &n, &m);

        while(m--){

            int x, y, w;

            scanf("%d%d%d", &x, &y, &w);

            addedge(x, y, w);

        }

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

        printf("%d\n", ek(, n));

    }

    return ;

}