285484026

「网络流 24 题」负载平衡
「网络流 24 题」负载平衡题解:从源点向每个物品大于平均值的的点连边权值为0,容量为data[i]-ans,然后...
扫描右侧二维码阅读全文
25
2018/10

「网络流 24 题」负载平衡

「网络流 24 题」负载平衡
题解:从源点向每个物品大于平均值的的点连边权值为0,容量为data[i]-ans,然后从每个物品小于平均值的向汇点连边ans-data[i],然后从每个点向相邻的两个点连容量为INF,权值为1的边

#include <bits/stdc++.h>

const int MAXN = 1000000,INF = 10000000;

using namespace std;

int n,sum,s,t,e = 2,cnt,ans;
int data[MAXN],pos[MAXN],head[MAXN],pri[MAXN],dis[MAXN];
bool inq[MAXN]; 

struct node{
    int u,v,w,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int w,int c)
{
    edge[e] = (node){u,v, w,c,0,head[u]};head[u] = e++;
    edge[e] = (node){v,u,-w,0,0,head[v]};head[v] = e++;
}

inline void init()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&data[i]);
        sum += data[i];
    }
    
    s = 0;t = n+1;ans = sum / n;

    for(int i = 1;i <= n;i++){    
        if(data[i] > ans) addedge(s,i,0,data[i]-ans);    
    
        if(data[i] < ans) addedge(i,t,0,ans-data[i]);    
                
        int u = (i-1) == 0   ? n : i-1;
        int v = (i+1) == n+1 ? 1 : i+1;
        addedge(i,u,1,INF);
        addedge(i,v,1,INF);
    } 
}

queue<int>Q;
inline bool spfa(){
    for(int i = s;i <= t;i++){
        inq[i] = false;
        dis[i] = INF;
        pri[i] = 0;
    }
    Q.push(s);dis[s] = 0;inq[s] = true;
    while(!Q.empty()){
        int x = Q.front();Q.pop();inq[x] = false;
        for(int i = head[x];i;i = edge[i].next){
            node E = edge[i];
            if(dis[E.v] > dis[x] + E.w && E.c > E.f){
                dis[E.v] = dis[x] + E.w;
                pri[E.v] = i;
                if(!inq[E.v]){
                    Q.push(E.v);
                    inq[E.v] = true;
                }
            }
        }
    }
    return pri[t] ? true : false;
}

inline int MCMF()
{
    int tmp,cost = 0,flow = 0;
    while(spfa())
    {
        tmp = INF;
        for(int i = pri[t];i;i = pri[edge[i^1].v])
          tmp = min(edge[i].c-edge[i].f,tmp);
        for(int i = pri[t];i;i = pri[edge[i^1].v]){
            edge[i].f += tmp;
            edge[i^1].f -= tmp;
            cost += tmp*edge[i].w;
        }
        flow += tmp;
    }
    return cost;
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();
    
    printf("%d\n",MCMF());
    return 0;
}
Last modification:October 25th, 2018 at 03:03 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment