Dinic模板
如题= =自用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter (System.out);
while(sc.hasNext()){
int m=sc.nextInt();
int n=sc.nextInt();
Dinic dinic =new Dinic(n);
for(int i=1;i<=m;i++){
int x=sc.nextInt();
int y=sc.nextInt();
int z=sc.nextInt();
dinic.maze[x][y]+=z;
}
long sum=0;
long temp=0;
while(dinic.bfs()){
while((temp=dinic.find(1, 0x7fffffff))!=0)sum+=temp;
}
pw.println(sum);
pw.flush();
}
}

}
class Dinic{/*普通:O(V^2E) 二分图O(sqrt(V)E)*/
int[][]maze;
int[]dis;
int[]q=new int[4000];
int h,r;
int n,m,ans;//n:dian m:bian 1-n
Dinic(int n){
maze=new int[n+1][n+1];
dis=new int[n+1];
this.n=n;
}
boolean bfs(){
int i=0,j=0;
Arrays.fill(dis, -1);
dis[1]=0;
h=0;
r=1;
q[1]=1;
while(h<r){
j=q[++h];
for(i=1;i<=n;i++){
if(dis[i]<0&&maze[j][i]>0){
dis[i]=dis[j]+1;
q[++r]=i;
}
}
}
if(dis[n]>0)return true;
else return false;
}
//Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广
//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量
int find(int x,int low){
int i,a=0;
if(x==n)return low;
for(i=1;i<=n;i++){
if(maze[x][i]>0
&&dis[i]==(dis[x]+1)
&&((a=find(i,Math.min(low, maze[x][i])))!=0)){
maze[x][i]-=a;
maze[i][x]+=a;
return a;
}
}
return 0;
}
}