题目大意:
G 公司有 n 个沿铁路运输线环形排列的仓库, 每个仓库存储的货物数量不等. 如何用最少搬运量可以使
n 个仓库的库存数量相同. 搬运货物时, 只
能在相邻的仓库之间搬运.
思路:
最小费用最大流.
假设物品的总库存之和为 sum, 那么为了使库存之和相等, 搬运结束后每一个仓库的目标库存量 ave 应该都等于 sum/n.
这时候很显然, 我们发现初始库存量 > ave 的仓库会向其他仓库搬运货物, 而初始库存量 < ave 的仓库会接收货物.
所以我们将所有仓库的初始货物数 nums[i] 减去 ave, 如果 nums[i]-ave>0, 那么由超级源点向他发出一条流量为 nums[i]-ave, 费用为 0 的边.
如果 nums[i]-ave<0, 那么由他向超级汇点发出一条流量为 ave-nums[i], 费用为 0 的边.
最后再在所有相邻的仓库之间互相建立流量为无穷大, 费用为 1 的双向边.
然后就没有然后了...
我的错误 o(﹏)o
1, 一开始直接跑了最大流, 结果 WA 了 9 个点, 后来发现最大流无法计算转移量之和, 其实这是一个很蠢的错误,,,
2, 加双向边的时候有一个细节, 因为我用的是邻接表, 一开始加双向边的时候没有加入费用为负的辅助边, 结果还是 WA 了 9 个点...
代码:
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <queue>
- using namespace std;
- #define MAXN 110
- struct Node{
- int u,v,w,c;
- Node(){}
- Node(int u,int v,int w,int c):u(u),v(v),w(w),c(c){}
- }p[MAXN<<3];
- struct Record{
- int u,dis;
- Record(){}
- Record(int u,int dis):u(u),dis(dis){}
- bool operator <(const Record & a) const{
- return dis>a.dis;
- }
- };
- int head[MAXN],Next[MAXN<<3],nums[MAXN],dis[MAXN],pre[MAXN],preNode[MAXN];
- bool vis[MAXN];
- int i,j,k,m,n,tot,sum;
- void addNode(int u,int v,int w,int c){
- p[++tot]=Node(u,v,w,c);
- Next[tot]=head[u],head[u]=tot;
- p[++tot]=Node(v,u,0,-c);
- Next[tot]=head[v],head[v]=tot;
- }
- bool dijkstra(int src,int goal){
- priority_queue<Record> mque;
- while(!mque.empty()) mque.pop();
- for(register int i=0;i<=n+1;i++) vis[i]=false,dis[i]=1000000000;
- mque.push(Record(src,0));
- vis[src]=true; dis[src]=0;
- pre[src]=-1;
- while(!mque.empty()){
- Record tmp=mque.top(); mque.pop();
- if(dis[tmp.u]<tmp.dis) continue;
- //if(vis[tmp.u]) continue;
- for(register int i=head[tmp.u];i+1;i=Next[i]){
- if(p[i].w&&dis[tmp.u]+p[i].c<dis[p[i].v]){
- pre[p[i].v]=tmp.u;
- preNode[p[i].v]=i;
- dis[p[i].v]=dis[tmp.u]+p[i].c;
- mque.push(Record(p[i].v,dis[p[i].v]));
- }
- }
- }
- if(dis[goal]!=1000000000) return true;
- return false;
- }
- int dinic(int src,int goal){
- int ans=0;
- while(dijkstra(src,goal)){
- int minf=1000000000;
- for(register int i=goal;i!=src;i=pre[i]){
- minf=min(minf,p[preNode[i]].w);
- }
- for(register int i=goal;i!=src;i=pre[i]){
- p[preNode[i]].w-=minf;
- p[preNode[i]^1].w+=minf;
- }
- ans+=dis[goal]*minf;
- }
- return ans;
- }
- int main(){
- scanf("%d",&n);
- sum=0;
- for(i=1;i<=n;i++) scanf("%d",nums+i),sum+=nums[i];
- sum/=n;
- for(i=0;i<=n+1;i++) head[i]=-1;
- tot=-1;
- for(i=1;i<=n;i++) nums[i]-=sum;
- for(i=1;i<=n;i++) if(nums[i]>0) addNode(0,i,nums[i],0); else { if(nums[i]<0) addNode(i,n+1,-nums[i],0); }
- for(i=1;i<=n-1;i++) addNode(i,i+1,10000000,1),addNode(i+1,i,10000000,1);
- addNode(n,1,10000000,1),addNode(1,n,10000000,1);
- printf("%d\n",dinic(0,n+1));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2741088.html