最大流(dinic算法)

时间:2022-10-17 04:30:14

题目来源Drainage Ditches HDU - 1532 ,裸的最大流
代码:
选用dinic有如下优势
1.代码量小,容易记忆。
2.效率上比EK算法快很多,虽然比asp稍慢,但是是可以接受的。

import java.util.Arrays;
import java.util.Scanner;

public class Main {   
    final static int maxn=200;
    final static int maxx=400;
    final static int INF =0x3f3f3f3f;
    static int cnt;
    static int head[]=new int[maxn];
    static int to[]=new int[maxx],flow[]=new int[maxx],next[]=new int[maxx];
    static void addEdge(int x,int y,int cap)
    {
        to[cnt]=y;flow[cnt]=cap;next[cnt]=head[x];head[x]=cnt++;
        to[cnt]=x;flow[cnt]=0;next[cnt]=head[y];head[y]=cnt++;
    }
    static int vis[]=new int[maxn];
    static int pre[]=new int[maxn];
    static int que[]=new int[maxn];
    static boolean bfs(int s,int e)
    {
        int L=0,R=0;
        pre[s]=-1;
        Arrays.fill(vis, -1);
        que[R++]=s;
        vis[s]=0;
        while(L<R)
        {
            int u=que[L++];
            for(int i=head[u];i>=0;i=next[i])
            {
                int v=to[i];
                if(vis[v]==-1&&flow[i]>0)
                {
                    vis[v]=vis[u]+1;
                    if(v==e)
                        return true;
                    que[R++]=v;
                }
            }
        }
        return false;
    }
    static int dfs(int s,int t,int f)
    {
        if(s==t||f==0)
            return f;
        int r=0;
        for(int i=head[s];i>=0;i=next[i])
        {
            int v=to[i];
            if(vis[v]==vis[s]+1&&flow[i]>0)
            {
                int d=dfs(v,t,Math.min(f, flow[i]));
                if(d>0)
                {
                    flow[i]-=d;
                    flow[i^1]+=d;
                    r+=d;
                    f-=d;
                    if(f==0)break;
                }
            }
        }
        if(r==0)
            vis[s]=INF;
        return r;
    }
    static int maxFlow(int s,int e)
    {
        int ans=0;
        while(bfs(s,e))
            ans+=dfs(s,e,INF);
        return ans;
    }
    static void init()
    {
        Arrays.fill(head, -1);
        cnt=0;
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext())
        {
            int m=sc.nextInt();
            int n=sc.nextInt();
            init();
            for(int i=0;i<m;i++)
                addEdge(sc.nextInt(),sc.nextInt(),sc.nextInt());
            System.out.println(maxFlow(1,n));
        }
    }
}