非常感谢这道题，准确的来说应该是这道题的数据。这道题其实是很简单的。
题意：
一堆箱子围成一个圈，每个箱子里面初始没有或有几个球。要求最后每个箱子里面最多一个球。每次转移球只能转移到相邻的箱子，转移一个球，需要花费1。问最小花费。
思路：
最暴力的思路是每个球对其他所有球都建立一条边，费用为最短距离。
但是有个显然的特点是，a -> b 与 a-> k , k-> b 的花费是相同的。所以我们只要在相邻的箱子建边即可。容量 inf ，费用为 1 。
建立源点连接有球的箱子，容量为 球 数，花费为 0 。箱子到汇点容量为 1 ，花费为 0 。
AC Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2005;
const int maxe = 40005;
struct MCMF {
private:
int src, des, idx, ans, flow;
int head[maxn], dis[maxn], preID[maxe], que[maxe + 10];
bool inq[maxn];
struct node {
int to, next;
int flow, cost;
node() {}
node(int _to, int _next, int _flow, int _cost)
: to(_to)
, next(_next)
, flow(_flow)
, cost(_cost)
{
}
} edges[maxe];
bool spfa()
{
for (int i = src; i <= des; i++) {
dis[i] = inf;
inq[i] = false;
preID[i] = -1;
}
int u, l = 0, r = 1;
inq[src] = true;
dis[src] = 0;
que[0] = src;
while (l != r) {
u = que[l++];
if (l == maxe + 1)
l = 0;
for (int id = head[u]; ~id; id = edges[id].next) {
int v = edges[id].to;
if (edges[id].flow > 0 && dis[u] + edges[id].cost < dis[v]) {
dis[v] = dis[u] + edges[id].cost;
preID[v] = id;
if (!inq[v]) {
inq[v] = true;
if (dis[v] < dis[que[l]]) {
l--;
if (l == -1)
l = maxe;
que[l] = v;
} else {
que[r++] = v;
if (r == maxe + 1)
r = 0;
}
}
}
}
inq[u] = false;
}
return dis[des] != inf;
}
public:
void addEdge(int u, int v, int f, int c)
{
edges[idx] = node(v, head[u], f, c);
head[u] = idx++;
edges[idx] = node(u, head[v], 0, -c);
head[v] = idx++;
}
void init(int s, int e)
{
src = s, des = e;
memset(head, -1, sizeof head);
flow = ans = idx = 0;
}
int minCost()
{
while (spfa()) {
int mflow = inf;
for (int id = preID[des]; id != -1; id = preID[edges[id ^ 1].to])
mflow = min(mflow, edges[id].flow);
for (int id = preID[des]; id != -1; id = preID[edges[id ^ 1].to]) {
ans += mflow * edges[id].cost;
edges[id].flow -= mflow;
edges[id ^ 1].flow += mflow;
}
flow += mflow;
}
return ans;
}
} mcmf;
int main()
{
int T, n, num;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
mcmf.init(0, n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &num);
if (num)
mcmf.addEdge(0, i, num, 0);
mcmf.addEdge(i, n + 1, 1, 0);
mcmf.addEdge(i, i % n + 1, inf, 1);
mcmf.addEdge(i % n + 1, i, inf, 1);
}
printf("%d\n", mcmf.minCost());
}
return 0;
}
MCMF模板
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2005;
const int maxe = 40005;
struct MCMF {
private:
int src, des, idx, ans, flow;
int head[maxn], dis[maxn], preID[maxe], que[maxe + 10];
bool inq[maxn];
struct node {
int to, next;
int flow, cost;
node() {}
node(int _to, int _next, int _flow, int _cost)
: to(_to)
, next(_next)
, flow(_flow)
, cost(_cost)
{
}
} edges[maxe];
bool spfa()
{
for (int i = src; i <= des; i++) {
dis[i] = inf;
inq[i] = false;
preID[i] = -1;
}
int u, l = 0, r = 1;
inq[src] = true;
dis[src] = 0;
que[0] = src;
while (l != r) {
u = que[l++];
if (l == maxe + 1)
l = 0;
for (int id = head[u]; ~id; id = edges[id].next) {
int v = edges[id].to;
if (edges[id].flow > 0 && dis[u] + edges[id].cost < dis[v]) {
dis[v] = dis[u] + edges[id].cost;
preID[v] = id;
if (!inq[v]) {
inq[v] = true;
if (dis[v] < dis[que[l]]) {
l--;
if (l == -1)
l = maxe;
que[l] = v;
} else {
que[r++] = v;
if (r == maxe + 1)
r = 0;
}
}
}
}
inq[u] = false;
}
return dis[des] != inf;
}
public:
void addEdge(int u, int v, int f, int c)
{
edges[idx] = node(v, head[u], f, c);
head[u] = idx++;
edges[idx] = node(u, head[v], 0, -c);
head[v] = idx++;
}
void init(int s, int e)
{
src = s, des = e;
memset(head, -1, sizeof head);
flow = ans = idx = 0;
}
int minCost()
{
while (spfa()) {
int mflow = inf;
for (int id = preID[des]; id != -1; id = preID[edges[id ^ 1].to])
mflow = min(mflow, edges[id].flow);
for (int id = preID[des]; id != -1; id = preID[edges[id ^ 1].to]) {
ans += mflow * edges[id].cost;
edges[id].flow -= mflow;
edges[id ^ 1].flow += mflow;
}
flow += mflow;
}
return ans;
}
} mcmf;