首页 > 代码库 > 自己yy的fulkson最大流算法

自己yy的fulkson最大流算法

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
const int maxn=1e3+7;
//maxn means the max 
const int INF=~0u>>1;
struct node{
    int to,cap,rev;
    node(int _to,int _cap,int _rev):to(_to),cap(_cap),rev(_rev){}
};
vector<node> edge[maxn];
bool vis[maxn];
void add(int from,int to,int cap){
    edge[from].push_back(node(to,cap,edge[to].size()));
    edge[to].push_back(node(from,0,edge[from].size()-1));
}

//dfs 小心爆int
int dfs(int v,int t,int f){
    if(v==t) return f;
    int i;
    for(i=0;i<edge[v].size();++i){
        int p=edge[v][i].to;
        if(!vis[p]&&edge[v][i].cap>0){
            vis[p]=true;
            int flow=edge[v][i].cap;
            int d=dfs(p,t,min(flow,f));
            if(d>0){
                edge[v][i].cap-=d;
                edge[p][edge[v][i].rev].cap+=d;
                return d;
            }
            //vis[p]=false;//这里丢了
            //如果加上了对流量大于零的判断我们
            //完全可以不写这一句
        }
    }
    return 0;
}
int maxflow(int s,int t){
    int flow=0;
    for(;;){
        memset(vis,0,sizeof(vis));//这里丢了
        vis[s]=true;//这里丢了
        int f=dfs(s,t,INF);
        if(f==0) break;
        flow+=f;
    }
    return flow;
}
int n,s,t;
void print(){
    int i,j;
    //这样写必须保证s<=t
    for(i=s;i<=t;++i){
        printf("head:%d",i);
        for(j=0;j<edge[i].size();++j){
            node t=edge[i][j];
            printf("==>(%d,%d,%d)",t.to,t.cap,t.rev);
        }
        printf("\n");
    }
}
int main(){
    // printf("INF:%d\n",INF);
    scanf("%d",&n);
    //输入的有向边数量
    scanf("%d%d",&s,&t);
    int i,u,v,cap;
    for(i=0;i<n;++i){
        scanf("%d%d%d",&u,&v,&cap);
        add(u,v,cap);
    }
    print();
    int mx=maxflow(s,t);
    printf("==============\n");
    print();
    printf("maxflow:%d\n",mx);
    return 0;
}

 

自己yy的fulkson最大流算法