题目来源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));
}
}
}