Load Balancing Problem [Network Flow 24 Questions] [Flow Balancing]

Topic link: https://www.luogu.org/problem/P4016

First, each point eventually becomes an average. The original value i s s[i], and the average value is aver.

Then calculate the difference between each point and the average value. If the difference is positive, it means that there are some redundant goods at this point that can be given to the adjacent points. We call this point "small source point".

But there are many such points, there is only one source point in the network flow model, so we will build a super source point S.

S connects all these "small source points" with a capacity of | s[i]-aver | at a cost of 0.

Think about why this cost is zero, because the goods of |s[i]-aver| belong to I point, and what cost is needed. Only because there is only one source point in the network flow model, we have set a super source point to combine multiple "small source points".

 

So if s[i]-aver is negative, which means that this point needs to import | s[i]-aver | goods, let him connect to T, capacity | s[i]-aver | cost 0.

Next, the adjacent points are connected to the capacity inf, and the cost is 1 side.

 

The maximum flow corresponds to the average of all.

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
const int N = 300;
const int inf = 1e9;
int n,m,S,T,tot;
int head[N];
struct node{
    int v,cap,cost,nxt;
}edge[int(2e5+100)];
int dis[N],pre[N],last[N],flow[N],maxflow,mincost; //pre: precursor node last: the front edge flow connected by each point: the flow from the source point to that point
bool vis[N];
void ae(int u,int v,int cap,int cost){  //Forward Star Edging
    edge[++tot] = node{v,cap,cost,head[u]};
    head[u] = tot;
    edge[++tot] = node{u,0,-cost,head[v]};
    head[v] = tot;
}
bool spfa() {
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));  //2e9
    memset(vis,0,sizeof(vis));
    deque<int> q;
    q.push_back(S);
    vis[S] = 1; dis[S] = 0; pre[T] = -1;
    while(!q.empty()) {
        int u = q.front();
        q.pop_front();
        vis[u] = 0;
        for(int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            if(edge[i].cap>0&&dis[v]>dis[u]+edge[i].cost) {
                dis[v] = dis[u]+edge[i].cost;
                pre[v] = u;
                last[v] = i;
                flow[v] = min(flow[u],edge[i].cap);
                if(!vis[v]) {
                    vis[v] = 1;
                    if(dis[v]<=dis[u]) q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
    return pre[T] != -1;
}
void dinic(){
    while(spfa()){
        int now = T;
        maxflow += flow[T];
        mincost += flow[T]*dis[T];
        while(now!=S) {
            edge[last[now]].cap -= flow[T];
            edge[last[now]^1].cap += flow[T];
            now = pre[now];
        }
    }
    return ;
}
void init() {
    mincost = 0;
    maxflow = 0;
    tot = -1;
    memset(head,-1,sizeof(head));
}
int s[200],aver;
int main() {
   // freopen("a.txt","r",stdin);
    ios::sync_with_stdio(0);
    cin>>n;
    S = 0;T = n+1;
    init();
    rep(i, 1, n) {
        cin>>s[i];
        aver += s[i];
    }
    aver /= n;
    rep(i, 1, n) {
        s[i] -= aver;
        if(s[i]>0) ae(S,i,s[i],0);
        else ae(i,T,-s[i],0);

        if(i!=1) ae(i,i-1,inf,1);
        else ae(i,n,inf,1);
        if(i!=n) ae(i,i+1,inf,1);
        else ae(i,1,inf,1);
    }
    dinic();
    cout<<mincost;
    return 0;
}

 

Tags: network iOS

Posted on Wed, 09 Oct 2019 00:08:18 -0700 by Skara