P4016 负载平衡问题

题目描述

G 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n
个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

输入格式

第一行一个正整数 n，表示有 n 个仓库。

第二行 n 个正整数，表示 n 个仓库的库存量。

输出格式
输出最少搬运量。

输入输出样例
输入 #1复制

5
17 9 14 16 4

输出 #1复制

11

说明/提示
1≤n≤100。

题解：

和网络流啥关系。。。又是老婆饼里没老婆？

方法一：

环形均分纸牌问题，还是板子题，代码都是通用的。。

贪心+数论
这种题总感觉在哪见过。。。
我们先考虑一种弱化的题目
n个仓库排成一列，每个仓库都有一定数量货物a[i]，只能相邻仓库可以传递货物，问最少需要传递几次才可以使各仓库货物相等？（就是把原题中的环改成一个列）
总数为sum，平均每个仓库分到T=sum/n，b[ i ]= T - a[ i ] ( b[]表示距离标准还有多少)，只要b[i]>0就说明后面一定有b[x]<0,那当前i多余的货物就向后移动，其实也就是多退少补，最终移动总牌数
现在的问题是n个仓库围成一个圈，我们可以通过破圈成链来解决这个问题。环形均分纸牌问题可以发现一个性质：至少有两个仓库是不需要从彼此之间那得到卡牌，这样就可以从这两点破坏成链
如果这种方式不明白，可以看我的这个题解，有详细分析解答
博客讲解

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int maxn=1e6+4;
ll a[maxn];
int main()
{
   
	cin>>n;
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
   
		cin>>a[i];
		sum+=a[i];
	}
	sum/=n;
	for(int i=n;i>1;i--)
	{
   
		a[i]=sum-a[i]+a[i+1];//为啥是这个公式可以在我那个推到里面得到 
	}
	a[1]=0;
	sort(a+1,a+n+1);
	ll res=0;
	int mid=(n+1)/2;
	for(int i=1;i<=n;i++)
	{
   
		res+=abs(a[i]-a[mid]);
	} 
	cout<<res<<endl;
	return 0;
	
} 

方法二：

恕我才疏学浅真的是一道最小费用最大流的题目
1.源点是0，汇点是n+1，费用是指两个相邻仓库中的运输单价
2.为了让所有仓库都均等，我们就要让多的仓库送出货物，连向源点；少的仓库就要接受货物，连向汇点。且连接源汇点的费用是0
3.相邻的仓库之间依次连上一条容量为 INF ，花费为 1 的双向边，
4.因为存在环的情况，所以还要特别处理1号节点与n号节点
我们用样例做一下分析：

每个边都有两种颜色数字，一个表示花费，一个表示容量
源点为起点的边容量之和等于以重点为边容量之和
跑一边费用流就可以了

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 5001;
const int MAXM = 50001;
const int INf = 2147483647;
int n, m, s, t, edge_sum = 1;
int maxflow, mincost;
int dis[MAXN], head[MAXN], incf[MAXN], pre[MAXN];
int a[MAXN];
bool vis[MAXN];
struct Edge {
   
	int next, to, dis, flow;
}edge[MAXM << 1];
inline void addedge(int from, int to, int flow, int dis) {
   
	edge[++edge_sum].next = head[from];
	edge[edge_sum].to = to;
	edge[edge_sum].dis = dis;
	edge[edge_sum].flow = flow;
	head[from] = edge_sum;
}
inline bool spfa() {
   
	queue <int> q;
	memset(dis, -1, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	q.push(s);
	dis[s] = 0;//距离 
	vis[s] = 1;// 记录该点已询问过 
	incf[s] = 0x7fffffff;//记录路径上的最小流 
	while(!q.empty()) {
   
		int u = q.front();
		vis[u] = 0;
		q.pop();
		for(register int i = head[u]; i; i = edge[i].next) {
   
			if(!edge[i].flow) continue;
			int v = edge[i].to;
			if(dis[v] > dis[u] + edge[i].dis||dis[v]==-1) {
   
				dis[v] = dis[u] + edge[i].dis;
				incf[v] = min(incf[u], edge[i].flow);
				pre[v] = i;//记录前缀点 
				if(!vis[v])
				{
   
					vis[v] = 1;
					q.push(v);
				 } 
			}
		}
	}
	if(dis[t] == -1) return 0;
	return 1;
}
inline void EK() {
   
	while(spfa()) {
   
		int x = t;
		maxflow += incf[t];
		mincost += dis[t] * incf[t];
		int i;
		while(x != s) {
   
			i = pre[x];
			edge[i].flow -= incf[t];
			edge[i^1].flow += incf[t];//建立反向边 
			x = edge[i^1].to;
		}
	}
}
int main() {
   
	scanf("%d", &n);
	int sum = 0;
	for(register int i = 1; i <= n; ++i) 
	{
   
		scanf("%d",&a[i]);
		sum += a[i];
	}
	sum /= n;//算出平均值
	for(register int i = 1; i <= n; ++i) {
   
		if(a[i] < sum) {
   //如果需要运入就与s连边
			addedge(0, i, sum - a[i], 0);
			addedge(i, 0, 0, 0);
		} 
		else if(a[i] > sum) {
   //如果需要运出就与t连边
			addedge(i, n + 1, a[i] - sum, 0);
			addedge(n + 1, i, 0, 0);
		}
		//以上为与S，T相连，以下为与临点相连 
		if(i == 1) {
   //特判1,别忘了是无向图
			addedge(1, n, INf, 1);
			addedge(n, 1, 0, -1);
			addedge(n, 1, INf, 1);
			addedge(1, n, 0, -1);
		} 
		else {
   
			addedge(i-1, i, INf, 1);
			addedge(i, i-1, 0, -1);
			addedge(i, i-1, INf, 1);
			addedge(i-1, i, 0, -1);
		}
	}
	s = 0, t = n + 1;
	EK();
	printf("%d\n",mincost);
	return 0;
}