題目: UVa - 11506 - Angry Programmer
題目說明
有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線,希望 1 號節點連不上 M 號節點。給你破壞每個物件的花費,問需要的最小總花費多少。
UVA 11506 - Angry Programmer ( Mincut, Flow ) - 0w1
解題思路
最大流,依照上面的說明建邊後使用 Dinic 求解即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
| #include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; ++i) #define CLR(c) memset(c, 0, sizeof(c))
static auto __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
template <typename T> T QPOP(queue<T>& q) { T tmp = q.front(); q.pop(); return tmp; }
const int INF = (int)1e9; const int MXN = 102;
int S = 1, T; int rn[MXN][MXN]; int l[MXN];
int M, W;
void init() { CLR(rn); }
void read() { T = M * 2;
int u, v, c; FOR(i, 0, M - 2) cin >> u >> c, rn[u + M][u] = rn[u][u + M] = c;
FOR(i, 0, W) cin >> u >> v >> c, rn[u][v + M] = rn[v][u + M] = c; }
bool dinicBFS() { CLR(l);
queue<int> q; q.push(S); l[S] = 1;
while (!q.empty()) { int u = QPOP(q);
FOR(v, 0, T + 1) { if (l[v] || !rn[u][v]) continue; l[v] = l[u] + 1; q.push(v); } }
return l[T]; }
int dinicDFS(int u, int cp) { if (u == T) return cp;
int tmp = cp;
FOR(v, 0, T + 1 && tmp) { if (l[v] != l[u] + 1 || !rn[u][v]) continue; int bt = dinicDFS(v, min(rn[u][v], tmp)); rn[u][v] -= bt; rn[v][u] += bt; tmp -= bt; }
return cp - tmp; }
int maximumFlow() { int mf = 0; while (dinicBFS()) mf += dinicDFS(S, INF); return mf; }
void solve() { cout << maximumFlow() << '\n'; }
int main() { while (cin >> M >> W && !(!M && !W)) { init(); read(); solve(); } }
|
參考資料
UVA 11506 - Angry Programmer ( Mincut, Flow ) - 0w1