洛谷P4016 负载平衡问题 费用流

时间：2022-02-02 08:30:26

这道题还是很好的.

考察了选手对网络流的理解.

首先，任意两个相邻点之间的运货量时没有限制的.

我们可以将相邻点之间的流量建为无限大，单位费用设为 1，代表运输一个货物需耗费一个代价.

由于题目要求最后所有人的货物量都相同，则说明每个人在最后拥有的货物量一定是总货物量的平均数，我们设为 $w$.

考虑一个点开始是的货物量为 $a$，则讨论两种情况.

1. a > w，则说明 $a$ 需要向周围的站点送出 $a-w$ 个货物以达到供需平衡. 我们从源点向该点流进 (a-w) 的流量，费用为 0

2. a < w，则说明该点需要得到 $w - a$ 个货物的补给，那么就让该点向汇点流出 (w-a) 的流量，费用仍然为 0.

我们思考一下，为什么这样是对的 ？

我们发现，所有点 (a-w) 之和一定为 0. (因为总量是守恒的）

首先，考虑第一种情况.

由于一个点被源点流进了 $a-w$ 的流量，那么该点一定会流出 $a-w$ 的流量，那么该点会至少贡献 $a-w$ 的花费.

由于流量是可以流满的，所以该做法就是正确的

Code:

#include<cstdio>              //好题

#include<algorithm>

#include<vector>

#include<cstring>

#include<queue>

using namespace std;

const int maxn=500;

const int INF=1000000+23666;

typedef long long ll;

int A[maxn];

int s,t,n;

struct Edge{

	int from,to,cap,cost;

	Edge(int u,int v,int c,int f):from(u),to(v),cap(c),cost(f){}

};

struct MCMF{

    vector<Edge>edges;

    vector<int>G[maxn];

    int d[maxn],inq[maxn],a[maxn],flow2[maxn];

    queue<int>Q;

    ll ans=0;

    int flow=0;

    void addedge(int u,int v,int c,int f){

    	edges.push_back(Edge(u,v,c,f));    //正向弧

    	edges.push_back(Edge(v,u,0,-f));   //反向弧

    	int m=edges.size();

    	G[u].push_back(m-2);

    	G[v].push_back(m-1);

    }

    int SPFA(){

    	for(int i=0;i<=n;++i)d[i]=INF,flow2[i]=INF;

    	memset(inq,0,sizeof(inq));int f=INF;

    	d[s]=0,inq[s]=1;Q.push(s);

        while(!Q.empty()){

        	int u=Q.front();Q.pop();inq[u]=0;

        	int sz=G[u].size();

        	for(int i=0;i<sz;++i){

                  Edge e=edges[G[u][i]];

                  if(e.cap>0&&d[e.to]>d[u]+e.cost){

                      a[e.to]=G[u][i];

                      d[e.to]=d[u]+e.cost;

                      flow2[e.to]=min(flow2[u],e.cap);

                      if(!inq[e.to]){inq[e.to]=1;Q.push(e.to);}

                  }

        	}

        }

        if(d[t]==INF)return 0;

        f=flow2[t];

        flow+=f;

        int u=edges[a[t]].from;

        edges[a[t]].cap-=f;

        edges[a[t]^1].cap+=f;

        while(u!=s){

        	edges[a[u]].cap-=f;

        	edges[a[u]^1].cap+=f;

        	u=edges[a[u]].from;

        }

        ans+=(ll)(d[t]*f);

        return 1;

    }

    ll maxflow(){

        while(SPFA());

        return ans;

    }

   // ll getcost(){return ans;}

}op;

int main()

{

     int N;scanf("%d",&N);

     s=0,t=N+1,n=N+1;

     int sum=0,ave;

     for(int i=1;i<=N;++i){

          int a;scanf("%d",&a);

          A[i]=a;

          sum+=a;

     }

     ave=sum/N;

     for(int i=1;i<=N;++i)

     {

          int a=A[i]-ave;

          if(a>0)op.addedge(s,i,a,0);

          if(a<0)op.addedge(i,t,-a,0);

     }

     for(int i=2;i<N;++i)

     {

     	     op.addedge(i,i-1,INF,1);

     	     op.addedge(i,i+1,INF,1);

     }

     op.addedge(1,2,INF,1);

     op.addedge(1,N,INF,1);

     op.addedge(N,N-1,INF,1);

     op.addedge(N,1,INF,1);

     printf("%lld",op.maxflow());

     return 0;

}

　　

相关文章