传送门 ↬ \looparrowright ↬
题目描述
W \text{W} W 公司有 m m m 个仓库和 n n n 个零售商店。第 i i i 个仓库有 a i a_i a i 个单位的货物;第 j j j 个零售商店需要 b j b_j b j 个单位的货物。
货物供需平衡,即 ∑ i = 1 m a i = ∑ j = 1 n b j \sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j i = 1 ∑ m a i = j = 1 ∑ n b j 。
从第 i i i 个仓库运送每单位货物到第 j j j 个零售商店的费用为 c i j c_{ij} c ij 。
试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。
输入格式
第 1 1 1 行有 2 2 2 个正整数 m m m 和 n n n ,分别表示仓库数和零售商店数。
接下来的一行中有 m m m 个正整数 a i a_i a i ,表示第 i i i 个仓库有 a i a_i a i 个单位的货物。
再接下来的一行中有 n n n 个正整数 b j b_j b j ,表示第 j j j 个零售商店需要 b j b_j b j 个单位的货物。
接下来的 m m m 行,每行有 n n n 个整数,表示从第 i i i 个仓库运送每单位货物到第 j j j 个零售商店的费用 c i j c_{ij} c ij 。
输出格式
两行分别输出最小运输费用和最大运输费用。
输入输出样例
输入 #1
2 3
220 280
170 120 210
77 39 105
150 186 122
输出 #1
48500
69140
说明/提示
1 ⩽ n , m ⩽ 100 1 \leqslant n, m \leqslant 100 1 ⩽ n , m ⩽ 100 。
分析
仓库和零售商独立,形成二分图的模型,进而考虑转化为最小费用最大流模型。
设置超级源点 s s s 和超级汇点 t t t 。仓库节点编号为 1 ∼ n 1\sim n 1 ∼ n ,零售商节点编号为 n + 1 ∼ m + n n+1\sim m+n n + 1 ∼ m + n 。从 s s s 向各个仓库的节点连边,s s s 向节点 i i i 的边的容量为 a i a_i a i ,费用为 0 0 0 ;从各个零售商的节点向 t t t 连边,零售商节点 i i i 向 t t t 的边的容量为 b i − n b_{i-n} b i − n ,费用为 0 0 0 。接着在仓库和零售商之间建边,从仓库向各个零售商节点连边,容量为 + ∞ +\infty + ∞ ,仓库节点 i i i 向零售商节点 j j j 的边的边权为 c i , j − n c_{i,j-n} c i , j − n 。
根据样例建立的网络如下图,对于最小运输费用,求最小费用最大流即可。若要求最大运输费用,可以将费用取反,求一次最小费用最大流,再将结果取反输出。
代码
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 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 #include <cstdio> #include <queue> #include <cstring> #include <iostream> using namespace std;const int N=204 ;const int inf=0x3f3f3f3f ;struct E { int to; int cap; int cost; int Next; }edge[N*N<<1 ]; int tot,head[N];int n,m;int s,t;int dis[N],incf[N],pre[N];bool inqueue[N];int a[N];int b[N];int c[N][N];void init () ;inline void add_edge (int ,int ,int ,int ) ;bool SPFA () ;int MCMF () ;int main () { cin>>n>>m; init (); int i,j; for (i=1 ;i<=n;i++) scanf ("%d" ,a+i); for (i=1 ;i<=m;i++) scanf ("%d" ,b+i); for (i=1 ;i<=n;i++) { for (j=1 ;j<=m;j++) { scanf ("%d" ,&c[i][j]); } } for (i=1 ;i<=n;i++) add_edge (s,i,a[i],0 ); for (i=1 ;i<=n;i++) { for (j=1 ;j<=m;j++) { add_edge (i,j+n,inf,c[i][j]); } } for (i=1 ;i<=m;i++) add_edge (i+n,t,b[i],0 ); cout<<MCMF ()<<endl; init (); for (i=1 ;i<=n;i++) add_edge (s,i,a[i],0 ); for (i=1 ;i<=n;i++) { for (j=1 ;j<=m;j++) { add_edge (i,j+n,inf,-c[i][j]); } } for (i=1 ;i<=m;i++) add_edge (i+n,t,b[i],0 ); cout<<-MCMF ()<<endl; return 0 ; } void init () { memset (head,-1 ,sizeof (head)); s=0 ; t=n+m+1 ; tot=1 ; } inline void add_edge (int u,int v,int cap,int cost) { tot++; edge[tot].to=v; edge[tot].cap=cap; edge[tot].cost=cost; edge[tot].Next=head[u]; head[u]=tot; tot++; edge[tot].to=u; edge[tot].cap=0 ; edge[tot].cost=-cost; edge[tot].Next=head[v]; head[v]=tot; } bool SPFA () { queue<int >q; memset (dis,inf,sizeof (dis)); memset (inqueue,0 ,sizeof (inqueue)); q.push (s); dis[s]=0 ; inqueue[s]=1 ; incf[s]=inf; while (!q.empty ()) { int x=q.front (); q.pop (); inqueue[x]=0 ; for (register int i=head[x];~i;i=edge[i].Next) { if (!edge[i].cap) continue ; int y=edge[i].to; if (dis[y]>dis[x]+edge[i].cost) { dis[y]=dis[x]+edge[i].cost; incf[y]=min (incf[x],edge[i].cap); pre[y]=i; if (!inqueue[y]) { inqueue[y]=1 ; q.push (y); } } } } if (dis[t]==inf) return 0 ; else return 1 ; } int MCMF () { int maxflow,mincost; maxflow=mincost=0 ; while (SPFA ()) { int x=t; while (x!=s) { int y=pre[x]; edge[y].cap-=incf[t]; edge[y^1 ].cap+=incf[t]; x=edge[y^1 ].to; } maxflow+=incf[t]; mincost+=dis[t]*incf[t]; } return mincost; }