如题= =自用模板

费用流几个技巧 加源点和汇点 如果边限制经过次数 如每条边仅能经过一次 那么可以将这条边的流量设置为1 如果点限制次数 可拆点 将一个点拆成两个点 由一条费用为零流量为1的有向边相连
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
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);
		MCMF mc=new MCMF();
		while(sc.hasNext()){
			int n=sc.nextInt();
			int m=sc.nextInt();
			mc.init(n+2);
			for(int i=1;i<=m;i++){
				int a=sc.nextInt();
				int b=sc.nextInt();
				int w=sc.nextInt();
				mc.add_diredge(a, b, 1, w);
				mc.add_diredge(b, a, 1, w);
			}
			mc.add_diredge(0, 1, 2, 0);
			mc.add_diredge(n, n+1, 2, 0);
			int sum=mc.mcmf(0, n+1);
			if(sum==2){
				pw.println(mc.cost);
			}
			pw.flush();
		}
	}
}
class MCMF{
	int maxn=60100;
	int maxm=100200;
	int INF=0x3f3f3f3f;
	int N; //顶点的个数 下标从 0~n-1
	Edge[]p;
	int e,n,m,st,en,cost;
	int[]head,dis,pre;
	boolean[]vis;
	MCMF(){
		p=new Edge[maxm<<1];
		head=new int[maxn];
		dis=new int[maxn];
		pre=new int[maxn];
		vis=new boolean[maxn];
		for(int i=0;i<(maxm<<1);i++){
			p[i]=new Edge();
		}
	}
	void init(int n){
		N=n;
		e=0;
		Arrays.fill(head, -1);
	}
	void add_diredge(int u,int v,int cap,int cost){
		p[e].to=v; p[e].cap=cap; p[e].cost=cost;
		p[e].flow=0;p[e].next=head[u]; head[u]=e++;
		p[e].to=u;p[e].cap=0;p[e].cost=-cost;
		p[e].flow=0;p[e].next=head[v];head[v]=e++;
	}
	boolean spfa(int s,int t){
		int u,v;
		Queue<Integer>q=new LinkedList<Integer>();
		Arrays.fill(vis, false);
		Arrays.fill(pre, -1);
		for(int i = 0; i < N; ++i)dis[i]=INF;
		vis[s] = true;
		dis[s] = 0;
	    q.add(s);
	    while(!q.isEmpty()){
	        u = q.poll();
	        vis[u] = false;
	        for(int i = head[u]; i != -1; i = p[i].next){
	            v = p[i].to;
	            if(p[i].cap>p[i].flow &&dis[u] + p[i].cost<dis[v]){
	                dis[v] = dis[u] + p[i].cost;
	                pre[v] = i;
	                if(!vis[v]){
	                    q.add(v);
	                    vis[v]=true;
	                }
	            }
	        }
	     }
	     if(pre[t]==-1) return false;
	     return true;
	}
	//返回最大流 cost存的是最小费用
	int mcmf(int s,int t){
	    int flow = 0; // 总流量
		cost=0;
	    while(spfa(s,t)){
	        int Min=INF;
	        for(int i = pre[t]; i != -1; i = pre[p[i^1].to]){
	            if(Min>p[i].cap-p[i].flow) Min=p[i].cap-p[i].flow;
	        }
	        for(int i=pre[t];i!=-1;i=pre[p[i^1].to]){
	            p[i].flow += Min;
	            p[i^1].flow -= Min;
	            cost+=p[i].cost*Min;
	        }
	        flow+=Min;
	    }
	    return flow;
	}
}
class Edge{
	int to,cap,cost,next,flow;
}