题意就是
有一些盒子,放在一个圈上,每个盒子中有若干个球,球的总数不会比盒子的数量多。
现在规定相邻的盒子之间可以把球移动过去,每次可以移动一个球,问用最少的步骤使得每个盒子中的球不超过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做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Online Judge Problem solution VN.SPOJ
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ-Solutions:SPOJ算法问题的解决方案
My solution for some spoj problems
SPOJ-备份工具 介绍 在 Sphere Online Judge ( ) 中,您可以尝试所给的具有挑战性的问题。 它还使您能够查看和下载您自己的解决方案。 工具 SPOJ_BACKUP 备份所有已接受的提交并将它们保存在脚本所在的计算机位置。...
SPOJ( )上选定问题的解决方案
cp:一些SPOJ问题的解决方案
联系 Python中SPOJ问题的解决方案。
分机检查spoj用户的排名。 此扩展名有2个选项: - 在选择的比赛中显示用户排名 - 在选择比赛中最多可比较5个用户第一个在后台运行,并在每隔几分钟内更新,您可以设置自己(并默认为15分钟)。当您单击分机的徽标时...
检查SPOJ用户等级的扩展名。 这个扩展有两个选项: - 在选择比赛中显示用户等级 - 比较最多5个用户选择比赛 第一个在后台运行,每隔几分钟更新一次,您可以自己设置(默认为15分钟)。 第二个是当你点击分机的标志...
spoj MSTS kruskal +生成树
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
gcd(a,b)= d (d为素数,1,1)