# 題目: UVa 10594 - Data Flow
# 題目說明
給一個無向圖 G ，有 N 個點及 M 條邊，每條邊的 capacity 固定為 K 、有不同的 cost
題目要求將大小為 D 的資料從起點 S 傳到終點 T ，求最小的 cost
INPUT:
每筆測資第一行輸入兩個整數 N 、 M
接下來有 M 行，每行輸入三個整數 u 、 v 、 c ，代表 edge(u, v) 的 cost 為 c
最後輸入兩個整數 D 、 K
OUTPUT:
輸出最小的 cost ，若無法將所有 D 資料傳至終點則輸出 Impossible.
# 解題方法
此題的解題概念為 Minimum cost Maximum flowMaximum flow 的部分使用 Ford Fulkerson 演算法Minimum cost 則使用佇列最佳化的 bellman ford 演算法，又稱 Shortest Path Faster Algorithm ，簡稱 SPFA
基本上與 Maximum flow 的程式碼相同，只是搜尋起點 S 是否可以走到終點 T 時不再是隨便走，而是用 SPFA 找到 minimum cost 的路徑
由於所有邊的 capacity 固定，所以可視為所有 capacity = 1 跑 SPFA ，之後再乘以 K 即可，(目的是為了加速效率)
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <climits> | |
#include <queue> | |
#define vll vector<long long> | |
using namespace std; | |
static auto fast_io = [] | |
{ | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
return 0; | |
}(); | |
int N, M, D, K; | |
int _s = 1, _t; | |
vector<vll> capacity; | |
vector<vll> net; | |
vector<vll> cost; | |
vector< vector<int> > G; | |
vll dis; | |
vector<int> p; | |
void init() | |
{ | |
_t = N; | |
capacity.assign(110, vll(110, 0)); | |
net.assign(110, vll(110, 0)); | |
cost.assign(110, vll(110, 0)); | |
G.assign(110, vector<int>()); | |
p.assign(110, 0); | |
} | |
void read() | |
{ | |
long long u, v, c; | |
for (int i = 0; i < M; ++i) | |
{ | |
cin >> u >> v >> c; | |
G[u].emplace_back(v); | |
G[v].emplace_back(u); | |
cost[u][v] = cost[v][u] = c; | |
capacity[u][v] = capacity[v][u] = 1; | |
} | |
cin >> D >> K; | |
} | |
bool bellman() | |
{ | |
dis.assign(110, LLONG_MAX); | |
dis[_s] = 0; | |
queue<int> Q; | |
vector<bool> inQ(110, false); | |
Q.emplace(_s); | |
inQ[_s] = true; | |
while (!Q.empty()) | |
{ | |
long long u = Q.front(); | |
Q.pop(); | |
inQ[u] = false; | |
for (auto& v : G[u]) | |
{ | |
if (net[v][u] > 0 && dis[u] + (-cost[v][u]) < dis[v]) | |
dis[v] = dis[u] + (-cost[v][u]); | |
else if (capacity[u][v] > net[u][v] && dis[u] + cost[u][v] < dis[v]) | |
dis[v] = dis[u] + cost[u][v]; | |
else continue; | |
p[v] = u; | |
if (!inQ[v]) Q.emplace(v), inQ[v] = true; | |
} | |
} | |
if (dis[_t] == LLONG_MAX) return false; | |
else return true; | |
} | |
void updateflow(int u, int v, int c) | |
{ | |
if (v == _s) return; | |
net[u][v] += c; | |
net[v][u] -= c; | |
updateflow(p[u], u, c); | |
} | |
void maxflow() | |
{ | |
long long ret = 0; | |
while (bellman()) | |
{ | |
if (D > K) ret += dis[_t] * K; | |
else ret += dis[_t] * D; | |
D -= K; | |
updateflow(p[_t], _t, 1); | |
if (D <= 0) break; | |
} | |
if (D > 0) cout << "Impossible.\n"; | |
else cout << ret << "\n"; | |
} | |
int main() | |
{ | |
while (cin >> N >> M) | |
{ | |
init(); | |
read(); | |
maxflow(); | |
} | |
} |
# 參考資料
http://programming-study-notes.blogspot.com/2014/05/uva-10594-data-flow.html
https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E5%BF%AB%E9%80%9F%E7%AE%97%E6%B3%95
