盗了个最小费用流的模板，mark一下，改天消化一下－ －0
|
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
109
110
111
112 |
#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <vector>using
namespace std;int n,m;#define maxn 310#define maxe 202020#define INF 1<<30struct
node{ int
u,v,next,w,c;}edge[maxe];int
head[maxn],add;inline
int min(int
a,int b) { return
a>b?b:a; }struct
MinCostMaxFlow{ int
q[maxn],front,rear,add,vn; bool
vis[maxn]; int
cost[maxn]; int
in[maxn],pre[maxn]; void
init() { add=0; memset(head,-1,sizeof(head)); vn=n+10; } void
insert(int
u,int v,int w,int c) { edge[add].u=u; edge[add].v=v; edge[add].w=w; edge[add].c=c; edge[add].next=head[u]; head[u]=add++; edge[add].u=v; edge[add].v=u; edge[add].w=0; edge[add].c=-c; edge[add].next=head[v]; head[v]=add++; } bool
spfa(int
s,int e) { int
i,j; for(i=0;i<=vn;i++) cost[i]=INF; memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); cost[s]=0; pre[s]=-1; front=0,rear=1; q[front]=s; vis[s]=true; in[s]++; while(front!=rear){ int
u=q[front++],v; front%=maxn; vis[u]=false; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(edge[i].w>0&&cost[v]>cost[u]+edge[i].c) { cost[v]=cost[u]+edge[i].c; pre[v]=i; if(!vis[v]) { q[rear++]=v; rear%=maxn; vis[v]=true; in[v]++; if(in[v]>vn) return
false; } } } } if(cost[e]<INF) return
true; else
return false; } int
mincostmaxflow(int
s,int e) { int
mincost=0,i,j,maxflow=0; while(spfa(s,e)){ int
flow=INF; for(i=pre[e];i!=-1;i=pre[edge[i].u]) flow=min(flow,edge[i].w); maxflow+=flow; for(i=pre[e];i!=-1;i=pre[edge[i].u]){ edge[i].w-=flow; edge[i^1].w+=flow; } mincost+=cost[e]*flow; } return
mincost; }}net;int
val[maxn];int
main(){ int
i,j,s,e,sum,t,u,v,w; while(scanf("%d",&n)!=EOF) { for(sum=0,i=1;i<=n;i++)scanf("%d",&val[i]),sum+=val[i]; int
av=sum/n; net.init(); s=0; for(i=1;i<=n;i++) net.insert(s,i,val[i],0); t=n+1,e=n+2; for(i=1;i<=n;i++) net.insert(i,t,1,0),net.insert(i,e,av,0); for(i=1;i<n;i++) { scanf("%d %d %d",&u,&v,&w); u++; v++; net.insert(u,v,INF,w); net.insert(v,u,INF,w); } net.insert(t,e,sum-av*n,0); printf("%d\n",net.mincostmaxflow(s,e)); } return
0;} |
原文：http://www.cnblogs.com/chanme/p/3649389.html