网络流dinic ek模板 poj1273

这里只是用来存放模板，几乎没有讲解，要看讲解网上应该很多吧……

bfs不停寻找增广路到找不到为止，找到终点时用pre回溯，O(VE^2)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = ;

int cap[][], pre[], n, m, a[];

int bfs(){

    queue<int> q;

    q.push();

    memset(a,,sizeof(a));

    a[] = INF;

    while(!q.empty()){

        int front = q.front();

        q.pop();

        for(int i = ;i<=m;i++){

            if(!a[i] && cap[front][i]){

                a[i] = min(a[front], cap[front][i]);

                pre[i] = front;

                q.push(i);

            }

        }

    }

    return a[m];

}

int ek(){

    int ans = ;

    while(bfs()){

        ans += a[m];

        for(int i = m;i!=;i = pre[i]){

            cap[pre[i]][i] -= a[m];

            cap[i][pre[i]] += a[m];

        }

    }

    return ans;

}

int main(){

    while(~scanf("%d%d",&n,&m)){

        memset(cap,,sizeof(cap));

        for(int i = ;i<=n;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            cap[u][v] += w;

        }

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

    }

    return ;

}

dinic

反复构造层次网络加找增广路，优势在于当某点的流入量较大时，可以一次完成多条增广路的累加，O(V^2E)

记得初始化lv，cnt=1

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn = ;

const int INF = 0x3f3f3f3f;

struct EDGE{

    int to, next, cap, flow;

    EDGE(){}

    EDGE(int a, int b, int c, int d){

        to = a, next = b, cap = c, flow = d;;

    }

}e[];

int head[], cnt, lv[],m ,n;

void add(int from, int to, int cap){

    e[++cnt] = EDGE(to, head[from], cap, );

    head[from] = cnt;

    e[++cnt] = EDGE(from, head[to], , );

    head[to] = cnt;

}

int bfs(){

    queue<int> q;

    q.push();

    memset(lv,,sizeof(lv));

    lv[] = ;

    while(!q.empty()){

        int front = q.front();

        q.pop();

        for(int i = head[front];i;i = e[i].next){

            int to = e[i].to;

            if(!lv[to] && e[i].cap-e[i].flow){

                lv[to] = lv[front]+;

                q.push(to);

            }

        }

    }

    return lv[m];

}

int dfs(int now, int a){

    int flow = ,f;

    if(now == m) return a;

    for(int i = head[now];i;i = e[i].next){

        int to = e[i].to;

        if(lv[to] == lv[now]+ && (f = dfs(to,min(a,e[i].cap-e[i].flow)))){

            e[i].flow += f;

            e[i^].flow -= f;

            flow += f;

            a -= f;

            if(!a) break;

        }

    }

    return flow;

}

int dinic(){

    int ans = ;

    while(bfs()){

        ans += dfs(,INF);

    }

    return ans;

}

int main(){

    while(~scanf("%d%d",&n,&m)){

        cnt = ;

        memset(head,,sizeof(head));

        for(int i = ;i<=n;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            add(u,v,w);

        }

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

    }

    return ;

}

巴特西

网络流dinic ek模板 poj1273

最新文章

热门文章