LibreOJ #6013. 「网络流 24 题」负载平衡 最小费用最大流 供应平衡问题

#6013. 「网络流 24 题」负载平衡

内存限制:256 MiB时间限制:1000 ms标准输入输出
题目类型:传统评测方式:文本比较
上传者: 匿名

题目描述

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

输入格式

文件的第 1 11 行中有 1 11 个正整数 n nn,表示有 n nn 个仓库。
第 2 22 行中有 n nn 个正整数,表示 n nn 个仓库的库存量。

输出格式

输出最少搬运量。

样例

样例输入

5
17 9 14 16 4

样例输出

11

数据范围与提示

1≤n≤100 1 \leq n \leq 1001≤n≤100

题目链接:https://loj.ac/problem/6013

题意:中文题意,意思明显。

思路:这是一种供求平衡问题,与「网络流 24 题」餐巾计划 是同一种问题。即将一个点拆成2个点来处理,一个需求、一个输出,形成一个二分图。

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define PI acos(-1.0)
const int maxn=1e3+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;
const ll INF=1e13+;
struct edge
{
int from,to;
ll c,w;
};
vector<edge>es;
vector<int>G[maxn];
int pre[maxn];
ll dist[maxn];
inline void addedge(int u,int v,ll c,ll w)
{
es.push_back((edge)
{
u,v,c,w
});
es.push_back((edge)
{
v,u,,-w
});
int x=es.size();
G[u].push_back(x-);
G[v].push_back(x-);
} bool spfa(int s,int t)
{
static std::queue<int> q;
static bool inq[maxn];
memset(dist,INF,sizeof(ll)*maxn);
memset(inq,false,sizeof(bool)*maxn);
pre[s]=-;
dist[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
for(int i=; i<G[u].size(); i++)
{
edge e=es[G[u][i]];
if(e.c&&dist[e.to]>dist[u]+e.w)
{
pre[e.to]=G[u][i];
dist[e.to]=dist[u]+e.w;
if(!inq[e.to]) q.push(e.to),inq[e.to]=true;
}
}
}
return dist[t]<inf;
} ll dinic(int s,int t)
{
ll flow=,cost=;
while(spfa(s,t))
{
ll d=INF;
for(int i=t; i!=s; i=es[pre[i]].from)
d=min(d,es[pre[i]].c);
flow+=d;
cost+=d*dist[t];
for(int i=t; i!=s; i=es[pre[i]].from)
{
es[pre[i]].c-=d;
es[pre[i]^].c+=d;
}
}
return cost;
}
ll a[maxn];
int main()
{
int n;
scanf("%d",&n);
int s=,t=*n+;
ll sum=;
for(int i=; i<=n; i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
ll ave=sum/n;
for(int i=; i<=n; i++)
{
if(ave<a[i]) addedge(s,i,a[i]-ave,);
else if(a[i]<ave) addedge(i+n,t,ave-a[i],);
int l=i-,r=i+;
if(l<) l=n;
if(r>n) r=;
addedge(i,l,inf,),addedge(i,l+n,inf,);
addedge(i,r,inf,),addedge(i,r+n,inf,);
}
printf("%lld\n",dinic(s,t));
return ;
}

最小费用最大流 供求平衡问题

上一篇:TCP连接建立系列 — 客户端接收SYNACK和发送ACK


下一篇:LibreOJ #6008. 「网络流 24 题」餐巾计划 最小费用最大流 建图