# 題目: UVa 10330 - Power Transmission
# 題目說明
給 N 個點， M 條邊，每個點及邊上有 capacity
求此圖的 maximum flow
INPUT:
第一行輸入一個整數 N ，接著輸入 N 個整數，代表點 1 ~ N 的 capacity
輸入一個整數 M ，接著有 M 行，每行輸入 U 、 V 、 C 三個整數，代表點 U 與點 V 連線， capacity 為 C
輸入兩個整數 B 、 D
- 輸入
B個整數，代表B與起點相連 - 輸入
D個整數，代表D與終點相連
OUTPUT:
輸出 maximum flow
# 解題方法
此題的解題概念為 Maximum flow 、 Ford Fulkerson
點上的 capacity 可視為兩個相連的點，連線的 capacity 為點上的 capacity
接著跑 Ford Fulkerson 演算法，得出 maximum flow
# 參考程式碼
#include <iostream> | |
#include <memory.h> | |
#include <climits> | |
#include <queue> | |
using namespace std; | |
int N, M, U, V, C, B, D; | |
int _s = 0, _t; | |
int G[250][250]; | |
int P[250]; | |
bool vis[250]; | |
void fast_io() | |
{ | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
} | |
void init() | |
{ | |
memset(G, 0, sizeof(G)); | |
memset(P, 0, sizeof(P)); | |
} | |
void read_build() | |
{ | |
int a; | |
_t = N * 2 + 1; | |
for (int i = 1;i <= N; ++i) cin >> G[i][i + N]; | |
cin >> M; | |
while (M--) cin >> U >> V >> C, G[U + N][V] = C; | |
cin >> B >> D; | |
while (B--) cin >> a, G[_s][a] = INT_MAX; | |
while (D--) cin >> a, G[a + N][_t] = INT_MAX; | |
} | |
int findflow(int u, int v, int c) | |
{ | |
if (v == _s) return c; | |
c = findflow(P[u], u, min(G[u][v], c)); | |
G[u][v] -= c; | |
G[v][u] += c; | |
return c; | |
} | |
int maxflow() | |
{ | |
int ret = 0; | |
while (1) | |
{ | |
memset(vis, false, sizeof(vis)); | |
queue<int> Q; | |
Q.emplace(_s); | |
vis[_s] = true; | |
while (!Q.empty() && !vis[_t]) | |
{ | |
int u = Q.front(); | |
Q.pop(); | |
for (int i = 0; i <= _t; ++i) if (!vis[i] && G[u][i] > 0) | |
{ | |
Q.emplace(i); | |
vis[i] = true; | |
P[i] = u; | |
} | |
} | |
if (!vis[_t]) break; | |
ret += findflow(P[_t], _t, INT_MAX); | |
} | |
return ret; | |
} | |
int main() | |
{ | |
fast_io(); | |
while (cin >> N) | |
{ | |
init(); | |
read_build(); | |
cout << maxflow() << "\n"; | |
} | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa-10330/
