題目: UVa - 10330 - Power Transmission
題目說明
基哥上課講過了。
解題思路
最大流,可使用 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 111 112 113 114
| #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 = 205;
int S, T; int rn[MXN][MXN]; int l[MXN];
int N;
void init() { CLR(rn); }
void read() { FOR(i, 1, N + 1) cin >> rn[i][i + N];
int u, v, w, m; cin >> m; while (m--) cin >> u >> v >> w, rn[u + N][v] = w;
int I, O; T = 2 * N + 1; cin >> I >> O; while (I--) cin >> v, rn[S][v] = INF; while (O--) cin >> u, rn[u + N][T] = INF; }
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 >> N) { init(); read(); solve(); } }
|