摸鱼第一,干活第二

It's time for BOOM!(ノ≧∀≦)ノ

【网络流24题】②负载平衡问题

系列第二弹。


网络流24题之第二题——负载平衡问题

原题见洛谷P4016


题解

裸的最小费用最大流。

题目求我们平均分配所有的货物,所以必定有一些仓库货物过剩,有一些则缺货,所以我们可以把所有仓库划分成两部分,过剩的与源点S相连,流量为过剩的货物数量,费用为0,缺货的与汇点T相连,流量为缺货的数量,费用同样为0。

然后根据题目,所有的节点是环形排列,两两之间运输,我们就在这些节点间建双向边,流量无限,费用为1。

这样一来,当整个网络已经没有增广路时,所有的货物也就均分完了。


流量算法——修改版SPFA

简单提一下,用SPFA跑剩余流量图的最小费用路线并记录,然后根据记录的路线修改流量以及计算总费用。

其实这中方法也可以打裸的最大流,而且比ISAP更好记。

才不是因为ISAP跑不了最小费用最大流

或许是我不知道怎样用ISAP跑这道题吧


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define il inline
#define inf 0x3F3F3F3F

//快速读入
char gtc();
int rdI();

//链式前向星
struct nd{
    int to,fm,cp,cs,nx;
} edge[605];
int top=2;
int head[105];
void addEdge(int,int,int,int);

//队列
int h,t;
int q[205];
void queueReset();
void queuePush(int);
int queuePop();

//最小费用最大流
int mnc;
int dis[105],pre[105];
bool isi[105];
bool spfa();
void mncf();

int N,tot;
int a[105];

int main(){
    N=rdI();
    for(int i=1;i<=N;++i)
        tot+=(a[i]=rdI());
    tot/=N;//平均数
    //建图连边
    for(int i=1;i<=N;++i)
        if(a[i]>tot)
            addEdge(0,i,a[i]-tot,0);
        else
            addEdge(i,N+1,tot-a[i],0);
    for(int i=1;i<N;++i){
        addEdge(i,i+1,inf,1);
        addEdge(i+1,i,inf,1);
    }
    addEdge(N,1,inf,1);
    addEdge(1,N,inf,1);
    mncf();
    printf("%d",mnc);
    return 0;
}

il void mncf(){
    while(spfa()){//找增广路
        int mnf=inf;
        for(int i=pre[N+1];i;i=pre[edge[i].fm])//找最小流量
            mnf=min(mnf,edge[i].cp);
        for(int i=pre[N+1];i;i=pre[edge[i].fm]){//调整流量网络
            edge[i].cp-=mnf;
            edge[i^1].cp+=mnf;
            mnc+=mnf*edge[i].cs;//统计费用
        }
    }
}
il bool spfa(){//spfa找增广路
    memset(dis,0x3F,sizeof(dis));
    memset(isi,false,sizeof(isi));
    dis[0]=0;
    isi[0]=true;
    queueReset();
    queuePush(0);
    while(h!=t){//跑费用最短路
        int u=queuePop();
        isi[u]=false;
        for(int i=head[u];i;i=edge[i].nx){
            int v=edge[i].to;
            if(edge[i].cp&&dis[v]>dis[u]+edge[i].cs){
                pre[v]=i;//记录路线
                dis[v]=dis[u]+edge[i].cs;
                if(!isi[v]){
                    queuePush(v);
                    isi[v]=true;
                }
            }
        }
    }
    return dis[N+1]!=inf;
}
//队列操作=============
il int queuePop(){
    return ++h<205?q[h]:q[h=0];
}
il void queuePush(int _x){
    ++t<205?(q[t]=_x):(q[t=0]=_x);
}
il void queueReset(){
    h=t=0;
}
//=====================
il void addEdge(int _x,int _y,int _f,int _c){//插边
    edge[top]=(nd){_y,_x,_f,_c,head[_x]};
    head[_x]=top;
    //不要忘了反流边
    edge[++top]=(nd){_x,_y,0,-_c,head[_y]};
    head[_y]=top++;
}
il char gtc(){//代替getchar()
    static char buff[0xFFFFF],*p1=buff,*p2=buff;
    return p1==p2&&(p2=(p1=buff)+fread(buff,1,0xFFFFF,stdin),p1==p2)?EOF:*p1++;
}
il int rdI(){//快速读入整数
    int t=0;
    char c=gtc();
    while(c<'0'||c>'9')
        c=gtc();
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=gtc();
    }
    return t;
}

【END】

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code