[CODEVS1916] 负载平衡问题（最小费用最大流）

传送门

输入所有 a[i]，求出平均值 sum，每个 a[i] = sum

那么如果 a[i] > 0，从 s 向 i 连一条容量为 a[i] 费用为 0 的有向边

　　如果 a[i] < 0，从 i 向 t 连一条容量为 a[i] 费用为 0 的有向边

每个点 i 和它相邻的两个点连一条容量为 INF 费用为 1 的有向边

求出最小费用最大流即为答案

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define INF 1e9 6 #define N 1000001 7 #define min(x, y) ((x) < (y) ? (x) : (y)) 8 9 int n, cnt, s, t; 10 int a[101], dis[N], pre[N]; 11 int head[N], to[N << 1], val[N << 1], cost[N << 1], next[N << 1]; 12 bool vis[N]; 13 14 inline int read() 15 22 23 inline void add(int x, int y, int z, int c) 24 31 32 inline bool spfa() 33 57 } 58 } 59 } 60 return pre[t] ^ 1; 61 } 62 inline int dinic() 64 75 sum += dis[t] * d; 76 } 77 return sum; 78 } 79 80 int main() 81 91 sum /= n; 92 for(i = 1; i <= n; i++) a[i] = sum; 93 for(i = 1; i <= n; i++) 94 102 else if(i == n) 103 107 else 108 112 } 113 printf("%d\n", dinic()); 114 return 0; 115 }
View Code

上一篇：[POJ1611]The Suspects（并查集）

下一篇：[luoguP2147] [SDOI2008]Cave 洞穴勘测（并查集 || lct）

---

最小费用最大流 网络流