最小费用最大流模板

spfa版费用流：
 1 //最小费用最大流spfa版，求最大费用只需要取相反数，结果取相反数即可。
 2 //点的编号0～n-1
 3 const int MAXN = 10000;
 4 const int MAXM = 100000;
 5 const int INF = 0x3f3f3f3f;
 6 struct Edge 
 7 {
 8     int to, next, cap, flow, cost;
 9 }edge[MAXM];
10 int head[MAXN], tol;
11 int pre[MAXN], dis[MAXN];
12 bool vis[MAXN];
13 int N;
14 void init(int n) 
15 {
16     N = n;
17     tol = 0;
18     memset(head, -1, sizeof(head));
19 }
20 void addedge(int u, int v, int cap, int cost) 
21 {
22     edge[tol].to = v; edge[tol].cap = cap;
23     edge[tol].cost = cost; edge[tol].flow = 0;
24     edge[tol].next = head[u]; head[u] = tol++;
25     edge[tol].to = u; edge[tol].cap = 0;
26     edge[tol].cost = -cost; edge[tol].flow = 0;
27     edge[tol].next = head[v]; head[v] = tol++;
28 }
29 bool spfa(int s, int t) 
30 {
31     queue<int> q;
32     for(int i = 0; i < N; i++) 
33     {
34         dis[i] = INF;
35         vis[i] = false;
36         pre[i] = -1;
37     }
38     dis[s] = 0; vis[s] = true;
39     q.push(s);
40     while(!q.empty()) 
41     {
42         int u = q.front();
43         q.pop();
44         vis[u] = false;
45         for(int i = head[u]; i != -1; i = edge[i].next)
46         { 
47             int v = edge[i].to;
48             if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) 
49             {
50                 dis[v] = dis[u] + edge[i].cost;
51                 pre[v] = i;
52                 if(!vis[v]) 
53                 {
54                     vis[v] = true;
55                     q.push(v);
56                 }
57             }
58         }
59     }
60     if(pre[t] == -1) return false;
61     else return true;
62 }
63 //返回的是最大流，cost存的是最小费用
64 int minCostMaxflow(int s, int t, int &cost) 
65 {
66     int flow = 0;
67     cost = 0;
68     while(spfa(s, t))
69     {
70         int Min = INF;
71         for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) 
72         {
73             if(Min > edge[i].cap - edge[i].flow)
74                 Min = edge[i].cap - edge[i].flow;
75         }
76         for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) 
77         {
78             edge[i].flow += Min;
79             edge[i^1].flow -= Min;
80             cost += edge[i].cost * Min;
81         }
82         flow += Min;
83     }
84     return flow;
85 }