记录编号	433440	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 负载平衡	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-08-05 15:06:50	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
#define MAXN 200
using namespace std;
struct Edge {
	int f, t, next, v, c;
}e[MAXN*MAXN];
int N, S, T, head[MAXN], cnt = 1, pre[MAXN], f[MAXN], dis[MAXN], ans;
bool vis[MAXN];
void Add_Edge(int from, int to, int cap, int cost) {
	e[++cnt].t = to;e[cnt].f = from;e[cnt].v = cap;e[cnt].c = cost;e[cnt].next = head[from];head[from] = cnt;
	e[++cnt].t = from;e[cnt].f = to;e[cnt].v = 0;e[cnt].c = -cost;e[cnt].next = head[to];head[to] = cnt;
}
bool SPFA() {
	queue<int>q;
	memset(dis, INF, sizeof(dis));
	q.push(S);dis[S] = 0;f[S] = INF;vis[S] = 1;
	while (!q.empty()) {
		int u = q.front();q.pop();vis[u] = 0;
		for (int i = head[u];i;i = e[i].next) {
			if (e[i].v&&dis[e[i].t] > dis[u] + e[i].c) {
				dis[e[i].t] = dis[u] + e[i].c;
				pre[e[i].t] = i;
				f[e[i].t] = min(f[u], e[i].v);
				if (!vis[e[i].t])q.push(e[i].t), vis[e[i].t] = 1;
			}
		}
	}
	if (dis[T] == INF)return 0;
	for (int i = pre[T];i;i = pre[e[i].f])e[i].v -= f[T], e[i^1].v += f[T];
	return 1;
}
int sb() {
	freopen("overload.in", "r", stdin);
	freopen("overload.out", "w", stdout);
	int ave = 0, a[MAXN];
	scanf("%d", &N);
	for (int i = 1;i <= N;i++) {
		scanf("%d", &a[i]);
		ave += a[i];
	}
	ave /= N;
	S = 0;T = N + 1;
	for (int i = 1;i <= N;i++) {
		if (a[i] > ave)
			Add_Edge(S, i, a[i] - ave, 0);
		else
			Add_Edge(i, T, ave - a[i], 0);
	}
	for (int i = 2;i < N;i++)Add_Edge(i, i - 1, INF, 1), Add_Edge(i, i + 1, INF, 1);
	Add_Edge(1, 2, INF, 1);Add_Edge(1, N, INF, 1);
	Add_Edge(N, N - 1, INF, 1);Add_Edge(N, 1, INF, 1);
	while (SPFA())
		ans += dis[T] * f[T];
	printf("%d", ans);
	return 0;
}
int chh = sb();
int main() { ; }