# 題目: UVa 12125 - March of the Penguins
# 題目說明
給一個座標圖，有 N 塊冰塊及數隻企鵝，要使企鵝全部跳到同一塊冰塊上，求哪幾塊可以？
INPUT:
第一行輸入一個整數 T 代表測資數
每筆測資第一行輸入 N 、 D ，代表冰塊的數量、企鵝能跳的距離
接下來有 N 行，每行輸入四個整數 x 、 y 、 n 、 m ，代表點 (x, y) 有 n 隻企鵝，能跳 m 次
OUTPUT:
求哪幾塊冰塊能使所有企鵝跳到上面
# 解題方法
此題的解題概念為 Maximum flow 、 Ford Fulkerson
將 S 連到所有冰塊上， capacity 為企鵝的數量
將每個冰塊連接到企鵝能跳的的冰塊上， capacity 為冰塊能跳的次數
最後依序將每個冰塊連到 T ，判斷所有企鵝是否都能跳至此
一樣利用 Edmonds-Karp 演算法解 maxflow 即可
# 參考程式碼
#include <iostream> | |
#include <memory.h> | |
#include <climits> | |
#include <queue> | |
#include <vector> | |
#include <math.h> | |
using namespace std; | |
int T, N, x, y, n, m, sum; | |
float D; | |
int _s = 0, _t; | |
vector<vector<int>> G, cpy; | |
vector<int> p, ans; | |
vector<pair<int, int>> ice; | |
vector<bool> vis; | |
void fast_io() | |
{ | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
} | |
void init() | |
{ | |
G.assign(250, vector<int>(250, 0)); | |
p.assign(250, 0); | |
ice.assign(250, { 0, 0 }); | |
ans.clear(); | |
sum = 0; | |
} | |
bool canjump(int i, int j) | |
{ | |
auto& [x1, y1] = ice[i]; | |
auto& [x2, y2] = ice[j]; | |
if (D * D - pow(x2 - x1, 2) - pow(y2 - y1, 2) > 0) return true; | |
return false; | |
} | |
void read_build() | |
{ | |
cin >> N >> D; | |
_t = N * 2 + 1; | |
for (int i = 1; i <= N; ++i) | |
{ | |
cin >> x >> y >> n >> m; | |
sum += n; | |
ice[i] = { x, y }; | |
G[_s][i] = n; | |
G[i][i + N] = m; | |
} | |
for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) | |
if (i != j && canjump(i, j)) G[i + N][j] = INT_MAX; | |
cpy = G; | |
} | |
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) | |
{ | |
vis.assign(250, false); | |
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(); | |
cin >> T; | |
while (T--) | |
{ | |
init(); | |
read_build(); | |
for (int i = 1; i <= N; ++i) | |
{ | |
G = cpy; | |
G[i][_t] = INT_MAX; | |
if (maxflow() == sum) ans.emplace_back(i - 1); | |
G[i][_t] = 0; | |
} | |
if (!ans.empty()) | |
{ | |
for (int i = 0; i < ans.size(); ++i) | |
{ | |
if (i) cout << " "; | |
cout << ans[i]; | |
} | |
cout << "\n"; | |
} | |
else cout << "-1\n"; | |
} | |
} |
# 參考資料
https://blog.csdn.net/llx523113241/article/details/47399521
