吐槽题目难度，这个题建模好像比前两个都要难，但是难度评级却比第二个要低。
解题思路
依旧是考虑如何建模和建立源点汇点。每个点的货物数量到最后都一样的话肯定是等于他们的平均值。用 $num$ 数组存储原来的货物数量，$tmp$ 是平均值。
如果 $num[i]-tmp$ 大于 $0$ 就表示这个点会免费多出一些货物，那就将源点与这个点相连。容量就是 $num[i]-tmp$，花费为 $0$ ；如果 $tmp-num[i]$ 大于 $0$ 就表示这个点需要从别的地方运进一些货物，就将这个点与汇点相连。容量就是 $tmp-num[i]$，花费为 $0$ ；再就每个点要和它左右两边的点相连，由于已经有上面的两种边作为限制。所以这里的容量直接设为 $INF$ ，花费为 $1$ 。
这就建好了图，这个最小的搬运量就等于在这个网络上的最小费用最大流。
附上代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
inline int read() {
int x =
0, f =
1;
char c =
getchar();
while (c <
'0' || c >
'9') {
if(c ==
'-') f = -
1; c =
getchar();}
while (c <=
'9' && c >=
'0') {x = x*
10 + c-
'0'; c =
getchar();}
return x *
f;
}
const int maxn =
25003, INF =
2147483647;
int n, num[
103], tmp, s, t, head[
105], cnt =
1, dis[
105], x[
105], pre[
105], Ans;
bool vis[
105];
struct edge {
int u, v, w, p, nxt;
}ed[maxn];
inline void addedge(
int u,
int v,
int w,
int p) {
ed[++cnt].nxt =
head[u];
ed[cnt].u = u, ed[cnt].v = v, ed[cnt].w = w, ed[cnt].p =
p;
head[u] =
cnt;
}
inline void add(
int u,
int v,
int w,
int p) {
addedge(u, v, w, p), addedge(v, u, 0, -
p);
}
inline bool SPFA() {
queue<
int>
Q;
for(
int i=
0; i<=n+
1; i++) dis[i] =
INF;
memset(vis, 0,
sizeof(vis));
vis[s] =
1, dis[s] =
0, Q.push(s);
int u;
while (!
Q.empty()) {
u =
Q.front();
Q.pop();
vis[u] =
0;
for(
int i=head[u]; i; i=
ed[i].nxt) {
if(dis[ed[i].v] > dis[u] + ed[i].p && ed[i].w >
0) {
dis[ed[i].v] = dis[u] +
ed[i].p;
pre[ed[i].v] =
i;
if(!
vis[ed[i].v]) {
vis[ed[i].v] =
1;
Q.push(ed[i].v);
}
}
}
}
if(dis[t] != INF)
return true;
return false;
}
inline void EK() {
int mn =
INF;
for(
int i=t; i!=s; i=
ed[pre[i]].u)
mn =
min(mn, ed[pre[i]].w);
for(
int i=t; i!=s; i=
ed[pre[i]].u) {
ed[pre[i]].w -=
mn;
ed[pre[i]^
1].w +=
mn;
Ans += ed[pre[i]].p *
mn;
}
}
int main() {
n =
read();
static int sum;
for(
int i=
1; i<=n; i++
) {
num[i] =
read();
sum +=
num[i];
}
tmp = sum /
n;
s =
0, t = n+
1;
for(
int i=
1; i<=n; i++) x[i] = num[i] -
tmp;
for(
int i=
1; i<=n; i++
) {
if(x[i] >
0) add(s, i, x[i],
0);
else add(i, t, -x[i],
0);
}
for(
int i=
1; i<=n; i++
) {
if(i !=
1) add(i, i-
1, INF,
1);
if(i != n) add(i, i+
1, INF,
1);
}
add(1, n, INF,
1), add(n,
1, INF,
1);
while (SPFA()) EK();
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9549272.html
