首页 > 代码库 > poj1273最大流dinc

poj1273最大流dinc

2024-07-14 07:10:19   213人阅读

bfs 构建层次图，dfs 寻找增广路。dfs在寻找增广路的同时自我调整直到此时的层次图无增广路时 重新构图，直到无增广路为止。

对于添加反弧，觉得对于每点 进流量和 出流量应该守恒，反向弧的添加方便自我调整，而通过每点的流量没变，最后导致流到终点的流量不变。

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;const int maxn= 222;const int INF=0xfffffff;int Min(int a,int b){    return a>b?b:a;}int Map[maxn][maxn];int n;int m;int l[maxn];int s;int e;bool  bfs(){    queue<int > q;    q.push(s);    memset(l,0,sizeof(l));    l[s]=1;    while(!q.empty()){        int cur=q.front(); q.pop();         for(int i=1;i<=m;i++){            if(!l[i]&&Map[cur][i]){                l[i]=l[cur]+1;                q.push(i);            }         }    }    return l[e];}int dfs(int x,int val){    int tem=val;    if(x==e) return val;    for(int i=1;i<=m&&tem;i++){        if(l[i]==l[x]+1&&Map[x][i]){            int t=dfs(i,Min(Map[x][i],tem));            Map[x][i]-=t;Map[i][x]+=t;            tem-=t;        }    }    return val-tem;}int solve(){    int ans=0;int t;    while(bfs()){        while(t= dfs(1,INF)){            ans+=t;        }    }    return ans;}int main(){    while(cin>>n>>m){        int a;int b;int c;        memset(Map,0,sizeof(Map));        for(int i=0;i<n;i++){            cin>>a>>b>>c; Map[a][b]+=c;        }        s=1;e=m;        cout<<solve()<<endl;    }    return 0;}

 


联系
我们