最小费用最大流的总结
P4016 负载平衡问题
题目链接
https://www.luogu.org/problem/P4016
解题思路
分源点、汇点,源点所有超过均值的点流量为1,费用为0、所有未超过均值的点连汇点流量为1,费用为0、相邻两点连边,流量为INF,费用为1,跑最小费用最大流即可。
AC代码
1 | 复制#include <bits/stdc++.h> |
2 | #define go(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) |
3 | #define dip(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) |
4 | #define maxn 2010 |
5 | #define maxm 1200010 |
6 | #define inf 0x3f3f3f3f |
7 | using namespace std; |
8 | struct Edge{ |
9 | int to, nex, cap, flow, cost; |
10 | }edge[maxm]; |
11 | int head[maxn], tol, pre[maxn], dis[maxn]; |
12 | bool vis[maxn]; |
13 | int N; |
14 | void init(int n){ |
15 | N = n; |
16 | tol = 0; |
17 | memset(head, -1, sizeof(head)); |
18 | } |
19 | void addedge(int u, int v, int cap, int cost){ |
20 | edge[tol].to = v; |
21 | edge[tol].cap = cap; |
22 | edge[tol].cost = cost; |
23 | edge[tol].flow = 0; |
24 | edge[tol].nex = head[u]; |
25 | head[u] = tol++; |
26 | edge[tol].to = u; |
27 | edge[tol].cap = 0; |
28 | edge[tol].cost = -cost; |
29 | edge[tol].flow = 0; |
30 | edge[tol].nex = head[v]; |
31 | head[v] = tol++; |
32 | } |
33 | bool spfa(int s, int t){ |
34 | queue<int>q; |
35 | for(int i = 0; i < N; i++){ |
36 | dis[i] = inf; |
37 | vis[i] = false; |
38 | pre[i] = -1; |
39 | } |
40 | dis[s] = 0; |
41 | vis[s] = true; |
42 | q.push(s); |
43 | while(!q.empty()){ |
44 | |
45 | int u = q.front(); |
46 | q.pop(); |
47 | vis[u] = false; |
48 | for(int i = head[u]; i != -1; i = edge[i].nex){ |
49 | int v = edge[i].to; |
50 | |
51 | if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost){ |
52 | dis[v] = dis[u] + edge[i].cost; |
53 | pre[v] = i; |
54 | if(!vis[v]){ |
55 | vis[v] = true; |
56 | q.push(v); |
57 | } |
58 | } |
59 | } |
60 | } |
61 | if(pre[t] == -1)return false; |
62 | else return true; |
63 | } |
64 | int minCostMaxflow(int s, int t, int &cost){ |
65 | int flow = 0; |
66 | cost = 0; |
67 | while(spfa(s, t)){ |
68 | int Min = inf; |
69 | for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]){ |
70 | if(Min > edge[i].cap - edge[i].flow) |
71 | Min = edge[i].cap - edge[i].flow; |
72 | } |
73 | for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]){ |
74 | edge[i].flow += Min; |
75 | edge[i^1].flow -= Min; |
76 | cost += edge[i].cost * Min; |
77 | } |
78 | flow += Min; |
79 | } |
80 | return flow; |
81 | } |
82 | int a[105]; |
83 | int main() |
84 | { |
85 | int n, sum = 0; |
86 | scanf("%d", &n); |
87 | init(n + 2); |
88 | go(i,1,n)scanf("%d", &a[i]), sum += a[i]; |
89 | sum /= n; |
90 | go(i,1,n){ |
91 | if(a[i] > sum)addedge(0, i, a[i] - sum, 0); |
92 | else addedge(i, n + 1, sum - a[i], 0); |
93 | } |
94 | go(i,1,n-1)addedge(i,i+1,inf,1),addedge(i+1,i,inf,1); |
95 | addedge(1,n,inf,1),addedge(n,1,inf,1); |
96 | int ans; |
97 | minCostMaxflow(0,n+1,ans); |
98 | printf("%d\n", ans); |
99 | return 0; |
100 | } |