大学生做静态网站,邢台精品网站建设,温州做网站软件,网站歌曲代码题目描述 GG 公司有 nn 个沿铁路运输线环形排列的仓库#xff0c;每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时#xff0c;只能在相邻的仓库之间搬运。 输入输出格式 输入格式#xff1a; 文件的第 11 行中有 11 个正整数 nn … 题目描述 GG 公司有 nn 个沿铁路运输线环形排列的仓库每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时只能在相邻的仓库之间搬运。 输入输出格式 输入格式 文件的第 11 行中有 11 个正整数 nn 表示有 nn 个仓库。 第 22 行中有 nn 个正整数表示 nn 个仓库的库存量。 输出格式 输出最少搬运量。 输入输出样例 输入样例#1 5 17 9 14 16 4 输出样例#1 11 说明 1 \leq n \leq 1001≤n≤100 解题思路 第一种方法就是环形均分纸牌和糖果传递一模一样。 第二种方法是网络流建立超级源点SS向比平均值大的连一条容量为a[i]-平均值花费为0的边建立超级源点T比平均值小的点向T连一条容量为平均值-a[i]花费为0的边然后每个点向它左右连一条容量为inf花费为1的边然后跑费用流即可。 代码 #includeiostream
#includecstdio
#includecstring
#includequeueusing namespace std;
const int MAXN 10005;
const int inf 0x3f3f3f3f;inline int rd(){int x0,f1;char chgetchar();while(!isdigit(ch)) {fch-?0:1;chgetchar();}while(isdigit(ch)) {x(x1)(x3)ch-0;chgetchar();}return f?x:-x;
}int n,a[MAXN],sum,head[MAXN],cnt1,S,T;
int to[MAXN1],nxt[MAXN1],val[MAXN1],cost[MAXN1];
int incf[MAXN],pre[MAXN],dis[MAXN],ans;
bool vis[MAXN];
queueint Q;inline void add(int bg,int ed,int w,int c){to[cnt]ed,nxt[cnt]head[bg],val[cnt]w,cost[cnt]c,head[bg]cnt;to[cnt]bg,nxt[cnt]head[ed],val[cnt]0,cost[cnt]-c,head[ed]cnt;
}bool spfa(){memset(vis,false,sizeof(vis));memset(dis,0x3f,sizeof(dis));while(Q.size()) Q.pop();dis[S]0,vis[S]1,Q.push(S),incf[S]inf;while(Q.size()){int xQ.front();Q.pop();for(register int ihead[x];i;inxt[i]){int uto[i];if(val[i] dis[x]cost[i]dis[u]){dis[u]dis[x]cost[i];pre[u]i;incf[u]min(incf[x],val[i]);if(!vis[u]) vis[u]1,Q.push(u);}}vis[x]0;}if(dis[T]inf) return false;return true;
}void update(){int xT;while(x!S){int ipre[x];val[i]-incf[T];val[i^1]incf[T];xto[i^1];}ansdis[T]*incf[T];
}int main(){nrd();S0,Tn1;for(register int i1;in;i) a[i]rd(),suma[i];sum/n;for(register int i1;in;i){a[i]-sum;if(a[i]0) add(S,i,a[i],0);else add(i,T,-a[i],0);}for(register int i2;in;i) add(i,i-1,inf,1),add(i,i1,inf,1);add(1,2,inf,1),add(1,n,inf,1);add(n,n-1,inf,1),add(n,1,inf,1);while(spfa()) update();coutansendl;return 0;
} 转载于:https://www.cnblogs.com/sdfzsyq/p/9676847.html
