# 題目: UVa 11506 - Angry Programmer
# 題目說明
給 M 個 node 與 W 條 edge 及他們的 capacity
求此圖的最小割
INPUT:
第一行輸入兩個整數 M 與 W ，代表有 M 個 node 與 W 條 edge
接下來有 M - 2 行，每行輸入兩個整數 U 、 C ，代表 node U 的 capacity 為 C
接下來有 W 行，每行輸入三個整數 U 、 V 、 C ，代表 edge U V 的 capacity 為 C
OUTPUT:
輸出此圖的最小割
# 解題方法
此題的解題概念為 Maximum flow 、 Ford Fulkerson
最小割可以轉換成最大流
點上的 capacity 可視為兩個相連的點， edge 的 capacity 為點上的 capacity
建完圖後跑 Edmonds-Karp 演算法即可
# 參考程式碼
#include <iostream> | |
#include <memory.h> | |
#include <climits> | |
#include <queue> | |
using namespace std; | |
int M, W, U, V, C; | |
int _s = 1, _t; | |
int G[150][150]; | |
int p[150]; | |
bool vis[150]; | |
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 node = M - 2; | |
int _u, _v; | |
_t = M + node; | |
for (int i = 0; i < node; ++i) | |
{ | |
cin >> U >> C; | |
G[U][U + node] = G[U + node][U] = C; | |
} | |
while (W--) | |
{ | |
cin >> U >> V >> C; | |
if (U == M) U = _t; | |
if (V == M) V = _t; | |
_u = (U != 1 && U != _t ? U + node : U); | |
_v = (V != 1 && V != _t ? V + node : V); | |
G[_u][V] = G[_v][U] = C; | |
} | |
} | |
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 = _s; 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 >> M >> W, !(!M && !W)) | |
{ | |
init(); | |
read_build(); | |
cout << maxflow() << "\n"; | |
} | |
} |
# 參考資料
https://blog.csdn.net/ac_lion/article/details/8643604
