大致题意:
有n个巧克力盒子摆成一圈,每个盒子中装有一定数量的巧克力,所有盒子中的巧克力的总数小于n。现在每次可以把一块巧克力从一个盒子移动到其相邻的盒子中,求最少移动几部才能使得每个盒子中最多只有一个巧克力。
大致思路:
很经典的构图。设源汇点,将每个盒子拆为两点a,a'。从源点想s连边,容量为盒子中巧克力的数量,费用为0。从 a->b'连边,容量为1,费用为0。对于两个盒子ab,如果a中的数量大于1,b中的数量等于0.则连接a->b',容量为1,费用为两个盒子之间的最短距离。a'向汇点连边,容量为1,费用为0。求出最小费用就是答案。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=99999999;
const int nMax=3000;
const int mMax=2000000;
struct{
int u,v, cap, cost, next, re;
}edge[mMax];
int ans,maxf;
int k,edgeHead[nMax];
int que[nMax],pre[nMax],dis[nMax];
bool vis[nMax],flag;
int K;
void addEdge(int u,int v,int ca,int co){////始点 终点 流量 花费
edge[k].v=v;
edge[k].cap=ca;
edge[k].cost=co;
edge[k].next=edgeHead[u];
edge[k].re=k + 1;
edgeHead[u]=k ++;
edge[k].v=u;
edge[k].cap=0;
edge[k].cost=-co;
edge[k].next=edgeHead[v];
edge[k].re=k - 1;
edgeHead[v]=k ++;
}
bool spfa(int s,int t,int n){ //始点,终点,总点数
int i, head = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方
for(i = 0; i <= n; i ++){
dis[i] = inf;////////////
vis[i] = false;
}
dis[s] = 0;
que[0] = s;
vis[s] = true;
while(head != tail){
int u = que[head];
for(i = edgeHead[u]; i != 0; 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[tail ++] = v;
if(tail == nMax) tail = 0;
}
}
}
vis[u] = false;
head++;
if(head ==nMax) head = 0;
}
if(dis[t] ==inf) return false;///////////
return true;
}
void end(int s,int t){
int u, p;
for(u = t;u!=s;u=edge[edge[p].re].v){
p = pre[u];
edge[p].cap-=1;
edge[edge[p].re].cap+=1;
ans+=edge[p].cost;
}
maxf+=1; //总流量
}
int box[nMax];
int abs(int a){
if(a>0)
return a;
return -a;
}
int main(){
int n,i,j,s,t;
while(scanf("%d",&n)!=EOF){
s=0,t=2*n+1;
k=1;
memset(edgeHead,0,sizeof(edgeHead));
for(i=1;i<=n;i++){
scanf("%d",&box[i]);
if(box[i]!=0)addEdge(s,i,box[i],0);
addEdge(i,i+n,1,0);
addEdge(i+n,t,1,0);
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(i==j||box[i]==0||box[j]!=0)continue;
addEdge(i,j+n,1,min(abs(i-j),n-abs(j-i)));
}
}
ans=maxf=0;
while(spfa(s,t,2*n+2)){
end(s,t);
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...
【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...
hdoj1004,解题代码,答案代码,欢迎下载
【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...
ACM ICPC HDOJ1000
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧