網(wǎng)絡(luò)流24題17. 運(yùn)輸問題

2019-11-06 06:20:03

字體：大中小

供稿：網(wǎng)友

運(yùn)輸問題

Description

W 公司有 m 個(gè)倉庫和 n 個(gè)零售商店。第 i 個(gè)倉庫有ai $a_i$ 個(gè)單位的貨物；第 j 個(gè)零售商店需要bj $b_j$ 個(gè)單位的貨物。貨物供需平衡，即Σai=Σbj $/Sigma a_i = /Sigma b_j$ 從第 i 個(gè)倉庫運(yùn)送每單位貨物到第 j 個(gè)零售商店的費(fèi)用為cij $c_{ij}$ 。試設(shè)計(jì)一個(gè)將倉庫中所有貨物運(yùn)送到零售商店的運(yùn)輸方案，使總運(yùn)輸費(fèi)用最少。對(duì)于給定的 m 個(gè)倉庫和 n 個(gè)零售商店間運(yùn)送貨物的費(fèi)用，計(jì)算最優(yōu)運(yùn)輸方案和最差運(yùn)輸方案。

Input

第 1 行有 2 個(gè)正整數(shù) m和 n，分別表示倉庫數(shù)和零售商店數(shù)。接下來的一行中有 m個(gè)正整數(shù)ai $a_i$ ，1≤i≤m，表示第 i 個(gè)倉庫有ai $a_i$ 個(gè)單位的貨物。再接下來的一行中有 n 個(gè)正整數(shù)bj $b_j$ ，1≤j≤n，表示第 j 個(gè)零售商店需要bj $b_j$ 個(gè)單位的貨物。接下來的 m行，每行有 n 個(gè)整數(shù)，表示從第 i 個(gè)倉庫運(yùn)送每單位貨物到第 j 個(gè)零售商店的費(fèi)用cij $c_{ij}$ 。

Output

輸出計(jì)算出的最少運(yùn)輸費(fèi)用和最多運(yùn)輸費(fèi)用。

Sample Input

2 3 220 280 170 120 210 77 39 105 150 186 122

Sample Output

48500 69140

題解

建圖：建立附加源S，附加匯T。 1.S向每個(gè)倉庫連接一條容量為倉庫貨物數(shù)量，費(fèi)用為0的邊。 2.每個(gè)商店向T連接一條容量為商店需要貨物數(shù)量，費(fèi)用為0的邊。 3.每個(gè)倉庫和每個(gè)商店之間連接一條容量無窮大，費(fèi)用為運(yùn)送費(fèi)用的邊。求出最小(大)費(fèi)用最大流就是答案。

#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 1000 + 10, M = 1000000 + 10, inf = 0x3f3f3f3f;struct Edge{ int fr, to, cap, flow, cost;}edg[M];int nxt[M], hd[N], tot;int n, m;int s, t;int q[N], inq[N], p[N], a[N], d[N];int wh[N], sp[N], val[N][N];void insert(int u, int v, int w, int x){ edg[tot].fr = u, edg[tot].to = v, edg[tot].cap = w, edg[tot].flow = 0, edg[tot].cost = x; nxt[tot] = hd[u]; hd[u] = tot; tot++; edg[tot].fr = v, edg[tot].to = u, edg[tot].cap = 0, edg[tot].flow = 0, edg[tot].cost = -x; nxt[tot] = hd[v]; hd[v] = tot; tot++;}void init(){ scanf("%d%d", &m, &n); s = 0, t = n + m + 1; int w; for(int i = 1; i <= m; i++) scanf("%d", &wh[i]); for(int i = 1; i <= n; i++) scanf("%d", &sp[i]); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) scanf("%d", &val[i][j]);}void build(){ tot = 0; memset(hd, -1, sizeof(hd)); for(int i = 1; i <= m; i++) insert(s, i, wh[i], 0); for(int i = 1; i <= n; i++) insert(i + m, t, sp[i], 0); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) insert(i, m + j, inf, val[i][j]);}bool spfa1(int &fl, int &cst){ for(int i = s; i <= t; i++) d[i] = inf; p[s] = 0; a[s] = inf; d[s] = 0; int head = 0, tail = 1; q[0] = s; inq[s] = 1; while(head != tail){ int u = q[head++]; if(head == 1001) head = 0; inq[u] = 0; for(int i = hd[u]; i >= 0; i = nxt[i]){ Edge &e = edg[i]; if(d[e.to] > d[u] + e.cost && e.cap > e.flow){ d[e.to] = d[u] + e.cost; p[e.to] = i; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]){ q[tail++] = e.to; if(tail == 1001) tail = 0; inq[e.to] = 1; } } } } if(d[t] == inf) return false; fl += a[t]; cst += a[t] * d[t]; int u = t; while(u != s){ edg[p[u]].flow += a[t]; edg[p[u]^1].flow -= a[t]; u = edg[p[u]].fr; } return true;}bool spfa2(int &fl, int &cst){ for(int i = s; i <= t; i++) d[i] = -inf; p[s] = 0; a[s] = inf; d[s] = 0; int head = 0, tail = 1; q[0] = s; inq[s] = 1; while(head != tail){ int u = q[head++]; if(head == 1001) head = 0; inq[u] = 0; for(int i = hd[u]; i >= 0; i = nxt[i]){ Edge &e = edg[i]; if(d[e.to] < d[u] + e.cost && e.cap > e.flow){ d[e.to] = d[u] + e.cost; p[e.to] = i; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]){ q[tail++] = e.to; if(tail == 1001) tail = 0; inq[e.to] = 1; } } } } if(d[t] == -inf) return false; fl += a[t]; cst += a[t] * d[t]; int u = t; while(u != s){ edg[p[u]].flow += a[t]; edg[p[u]^1].flow -= a[t]; u = edg[p[u]].fr; } return true;}void work(){ int flow = 0, cost = 0; build(); while(spfa1(flow, cost));