重在建图
第一直觉是入门题目分纸牌，那道题是贪心的。
但是网络流标签嘛就用网络流做了。
建图：（流量，费用）
1、超级源点 src + 超级汇点 sink
2、对于仓库 i，拆成 Ai 和 Bi 两个点
2 . 1、从 Ai 向 Bi 建立 （inf，0）
2 . 2、从 Bi 向 Ai-1 和 Ai+1 建边 （inf，1）
3、超级源点 和 Ai 建边 （库存，0）
4、Bi 和 超级汇点 建边 （avr，0）->（（（avr表示average）））
正确性：
由于费用流遵循在有流量的边中找最短路，那么它最开始“填掉”的边一定是费用为0的（如果本身有能力“填掉”的话），也就是 src->Ai->Bi ->sink 路径上的边；但如果有些仓库自身无法将均值边的流量“填掉”，也就是图依旧可以增广，那么就必须从其他地方运过来，那么就要经过费用为1的 Bi->Aj 的边，这将产生费用，由于是 spfa 最短路，那么当前求得的路径一定是最小的搬运费用。
增广终止的条件一定是 avr 的流量全部流满，也就是每个仓库最后达到均值的情况；否则一直增广，相当于一直搬运！
代码：
1 // luogu-judger-enable-o2 2 //AC，不开o2也AC 3 #include <bits/stdc++.h> 4 5 const int N = 1000 + 5 ; 6 7 std :: queue < int > q ; 8 9 int head [ N ] , nxt [ N ] , dis [ N ] , flt [ N ] , to [ N ] , cn = 1 ; 10 int pree [ N ] , pred [ N ] , c [ N ] ; 11 int src , sink , inf , n , m , x , mincost , avr ; 12 bool vis [ N ] ; 13 14 void create ( int u , int v , int f , int d ) { 15 cn ++ ; 16 to [ cn ] = v ; 17 dis [ cn ] = d ; 18 flt [ cn ] = f ; 19 nxt [ cn ] = head [ u ] ; 20 head [ u ] = cn ; 21 22 cn ++ ; 23 to [ cn ] = u ; 24 dis [ cn ] = - d ; 25 flt [ cn ] = 0 ; 26 nxt [ cn ] = head [ v ] ; 27 head [ v ] = cn ; 28 } 29 30 void prp ( ) { 31 int o [ 5 ] ; 32 memset ( o , 127 , sizeof ( o ) ) ; 33 inf = o [ 0 ] ; 34 } 35 36 bool spfa ( ) { 37 memset ( vis , false , sizeof ( vis ) ) ; 38 memset ( c , 127 , sizeof ( c ) ) ; 39 q . push ( src ) ; 40 c [ src ] = 0 ; vis [ src ] = true ; 41 while ( ! q . empty ( ) ) { 42 int tmp = q . front ( ) , v ; 43 q . pop ( ) ; vis [ tmp ] = false ; 44 for ( int i = head [ tmp ] ; i ; i = nxt [ i ] ) { 45 v = to [ i ] ; 46 if ( flt [ i ] && c [ v ] > c [ tmp ] + dis [ i ] ) { 47 c [ v ] = c [ tmp ] + dis [ i ] ; 48 pree [ v ] = i ; 49 pred [ v ] = tmp ; 50 if ( ! vis [ v ] ) { 51 q . push ( v ) ; 52 vis [ v ] = true ; 53 } 54 } 55 } 56 } 57 return c [ sink ] < inf ; 58 } 59 60 void augment ( ) { 61 int u = sink , delta = inf ; 62 while ( u != src ) { 63 if ( delta > flt [ pree [ u ] ] ) 64 delta = flt [ pree [ u ] ] ; 65 u = pred [ u ] ; 66 } 67 u = sink ; 68 while ( u != src ) { 69 flt [ pree [ u ] ] -= delta ; 70 flt [ pree [ u ] ^ 1 ] += delta ; 71 u = pred [ u ] ; 72 } 73 mincost += delta * c [ sink ] ; 74 } 75 76 77 int main ( ) { 78 scanf ( "%d" , & n ) ; 79 prp ( ) ; 80 src = 0 ; sink = 2 * n + 1 ; 81 for ( int i = 1 ; i <= n ; i ++ ) { 82 scanf ( "%d" , & x ) ; 83 create ( src , i , x , 0 ) ; 84 avr += x ; 85 } 86 avr /= n ; 87 88 for ( int i = 1 ; i <= n ; i ++ ) 89 create ( i , i + n , inf , 0 ) ; 90 for ( int i = n + 2 ; i < 2 * n ; i ++ ) 91 create ( i , i - n - 1 , inf , 1 ) , create ( i , i - n + 1 , inf , 1 ) ; 92 create ( n + 1 , 2 , inf , 1 ) , create ( n + 1 , n , inf , 1 ) ; 93 create ( n + n , 1 , inf , 1 ) , create ( n + n , n - 1 , inf , 1 ) ; 94 95 for ( int i = n + 1 ; i <= n + n ; i ++ ) 96 create ( i , sink , avr , 0 ) ; 97 while ( spfa ( ) ) 98 augment ( ) ; 99 printf ( "%d" , mincost ) ; 100 return 0 ; 101 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
