本文主要是介绍SPOJ 371 Boxes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意就是
有一些盒子，放在一个圈上，每个盒子中有若干个球，球的总数不会比盒子的数量多。
现在规定相邻的盒子之间可以把球移动过去，每次可以移动一个球，问用最少的步骤使得每个盒子中的球不超过1个
那么建图还是比较简单
源点跟每个点连接，容量为本来拥有的球数
每个点再与汇点连，容量为1
中间相邻的点之间连边，容量无穷，费用为1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{int v, cap, cost, next, re; // re记录逆边的下标。
} edge[MAXM];
int n, m, ans, flow, src, des;
int e, head[MAXN];
int que[MAXN], pre[MAXN], dis[MAXN];
bool vis[MAXN];
void init()
{e = ans = flow = 0;memset(head, -1, sizeof(head));
}
void add(int u, int v, int cap, int cost)
{edge[e].v = v;edge[e].cap = cap;edge[e].cost = cost;edge[e].next = head[u];edge[e].re = e + 1;head[u] = e++;edge[e].v = u;edge[e].cap = 0;edge[e].cost = -cost;edge[e].next = head[v];edge[e].re = e - 1;head[v] = e++;
}
bool spfa()
{int i, h = 0, t = 1;for(i = 0; i <= n; i ++){dis[i] = INF;vis[i] = false;}dis[src] = 0;que[0] = src;vis[src] = true;while(t != h){int u = que[h++];h %= n;vis[u] = false;for(i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(edge[i].cap && dis[v] > dis[u] + edge[i].cost){dis[v] = dis[u] + edge[i].cost;pre[v] = i;if(!vis[v]){vis[v] = true;que[t++] = v;t %= n;}}}}if(dis[des] == INF) return false;return true;
}
void end()
{int u, p, mi = INF;for(u = des; u != src; u = edge[edge[p].re].v){p = pre[u];mi = min(mi, edge[p].cap);}for(u = des; u != src; u = edge[edge[p].re].v){p = pre[u];edge[p].cap -= mi;edge[edge[p].re].cap += mi;ans += mi * edge[p].cost; // cost记录的为单位流量费用，必须得乘以流量。}flow += mi;
}
int nt;
void build()
{int w;scanf("%d", &nt);init();src = nt + 1;des = nt + 2;n = des;for(int i = 1; i <= nt; i++){scanf("%d", &w);add(src, i, w, 0);add(i, des, 1, 0);}for(int i = 1; i < nt; i++){add(i, i + 1, INF, 1);add(i + 1, i, INF, 1);}add(1, nt, INF, 1);add(nt, 1, INF, 1);
}
void MCMF()
{init();build();while(spfa()) end();
}
int main()
{int T;scanf("%d", &T);while(T--){MCMF();printf("%d\n", ans);}return 0;
}
这篇关于SPOJ 371 Boxes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
