1 typedef
long long ll;
2 const ll inf=
0x3f3f3f3f;
3 struct edge{
4 int x;
5 int y;
6 ll v;
//流量
7 ll c;
//费用
8 int nex;
9 }e[
1005];
10 ll flow,res;
11 int cnt,head[
505],n;
12 void adde(
int x1,
int x2,ll v1,ll v2){
13 e[cnt].c=
v2;
14 e[cnt].v=
v1;
15 e[cnt].x=
x1;
16 e[cnt].y=
x2;
17 e[cnt].nex=
head[x1];
18 head[x1]=cnt++
;
19 }
20 int dist[
505],prevv[
505],preve[
1005];
// 最短路的前驱节点 和 对应的边
21 inline
void min_cost_flow(
int s
/*源点*/,
int t
/*汇点*/)
22 {
23 ll f=
inf;
24 while(f >
0)
25 {
26 memset(dist,inf,
sizeof dist);
27 dist[s] =
0;
28 bool update =
true;
29 while(update)
30 {
31 update =
false;
32 for(
int i=
0;i<=n+
1;i++
)
33 {
34 if(dist[i] == inf)
continue;
35 for(
int j=head[i];j!=-
1; j=
e[j].nex)
36 {
37 if(e[j].v >
0 && dist[e[j].y] > dist[i] +
e[j].c)
38 {
39 dist[e[j].y] = dist[i] +
e[j].c;
40 prevv[e[j].y] =
i;
41 preve[e[j].y] =
j;
42 update =
true;
43 }
44 }
45 }
46 }
47 // 此时的 INF 表示再也没有 增广路径，于是就是最后的答案了!
48 if(dist[t] == inf)
break;
49 ll d =
f;
50 for(
int v0 = t; v0 != s; v0 =
prevv[v0])
51 {d =
min(d,e[preve[v0]].v);}
52 // d 就是 增广路的 流量！
53 f -=
d;
54 flow +=
d;
55 res += d *
dist[t];
56 for(
int v0=t;v0!=s;v0=
prevv[v0])
57 {
58 e[preve[v0]].v -=
d;
59 e[preve[v0]^
1].v += d;
//反向边流量加相应的值
60 }
61 }
62 }
转载于:https://www.cnblogs.com/MekakuCityActor/p/10673073.html
