这个网络流题挺简单的……

首先从[tex]S[/tex]向每个点连容量为该点存货量的边（费用为0）。首先注意最后所有存货量都要变成总的平均值，所以要从每个点向[tex]T[/tex]连一条容量为总的平均值的边（费用为0）。最后根据题目要求在相邻点之间连边（容量都是无限大，费用为1）。

跑一遍最小费用最大流，得出的费用就是答案。

代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110;
namespace MCMF{
	struct Edge{
        int u,v,cap,flow,cost;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap,int cost){
        edges.push_back((Edge){u,v,cap,0,cost});
        edges.push_back((Edge){v,u,0,0,-cost});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    int a[maxn];
    bool inQueue[maxn];
    int d[maxn],p[maxn];
    bool BellmanFord(int s,int t,long long& cost){
        register int i,u;
        queue<int> Q;
        memset(d,0x7f,sizeof(d));
        memset(inQueue,0,sizeof(inQueue));
        d[s]=0;
        inQueue[s]=true;
        p[s]=0;
        a[s]=0x7f7f7f7f;
        Q.push(s);
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
                    d[e.v]=d[u]+e.cost;
                    p[e.v]=G[u][i];
                    a[e.v]=min(a[u],e.cap-e.flow);
                    if(!inQueue[e.v]){
                        Q.push(e.v);
                        inQueue[e.v]=true;
                    }
                }
            }
        }
        if(d[t]==0x7f7f7f7f)
            return false;
        cost+=((long long)d[t])*((long long)a[t]);
        for(u=t;u!=s;u=edges[p[u]].u){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    long long MincostMaxflow(int s,int t){
        register long long ans=0;
        while(BellmanFord(s,t,ans));
        return ans;
    }
};

int A[maxn];
int main(){
	register int i,ave=0;
	int n;
	freopen("overload.in","r",stdin);
	freopen("overload.out","w+",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&A[i]);
		ave+=A[i];
		MCMF::AddEdge(0,i,A[i],0);
	}
	ave/=n;
	for(i=1;i<=n;i++){
		MCMF::AddEdge(i,n+1,ave,0);
		if(i>1){
			MCMF::AddEdge(i-1,i,0x7f7f7f7f,1);
			MCMF::AddEdge(i,i-1,0x7f7f7f7f,1);
		}
		if(i<n){
			MCMF::AddEdge(i+1,i,0x7f7f7f7f,1);
			MCMF::AddEdge(i,i+1,0x7f7f7f7f,1);
		}
	}
	MCMF::AddEdge(1,n,0x7f7f7f7f,1);
	MCMF::AddEdge(n,1,0x7f7f7f7f,1);
	printf("%lld\n",MCMF::MincostMaxflow(0,n+1));
	fclose(stdin);
	fclose(stdout);
	return 0;
}

• 相关文章
• 全局相关文章