diff options
| -rw-r--r-- | graph/dinicScaling.cpp | 74 | ||||
| -rw-r--r-- | graph/hopcroftKarp.cpp | 34 | ||||
| -rw-r--r-- | tcr.pdf | bin | 1095827 -> 669208 bytes |
3 files changed, 50 insertions, 58 deletions
diff --git a/graph/dinicScaling.cpp b/graph/dinicScaling.cpp index aecbddc..a795be1 100644 --- a/graph/dinicScaling.cpp +++ b/graph/dinicScaling.cpp @@ -1,63 +1,51 @@ -struct edge { - int from, to; +struct Edge { + int to, rev; ll f, c; }; -vector<edge> edges; -vector<vector<int>> adjlist; +vector<vector<Edge>> adj; int s, t; vector<int> pt, dist; -ll flow, lim; -queue<int> q; -void addEdge(int from, int to, ll c) { - adjlist[from].push_back(sz(edges)); - edges.push_back({from, to, 0, c}); - adjlist[to].push_back(sz(edges)); - edges.push_back({to, from, 0, 0}); +void addEdge(int u, int v, ll c) { + adj[u].push_back({v, (int)sz(adj[v]), 0, c}); + adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); } -bool bfs() { - dist.assign(sz(dist), -1); - dist[t] = sz(adjlist) + 1; - q.push(t); - while (!q.empty() && dist[s] < 0) { +bool bfs(ll lim) { + dist.assign(sz(adj), -1); + dist[s] = 0; + queue<int> q({s}); + while (!q.empty() && dist[t] < 0) { int cur = q.front(); q.pop(); - for (int id : adjlist[cur]) { - int to = edges[id].to; - if (dist[to] < 0 && - edges[id ^ 1].c - edges[id ^ 1].f >= lim) { - dist[to] = dist[cur] - 1; - q.push(to); + for (Edge& e : adj[cur]) { + if (dist[e.to] < 0 && e.c - e.f >= lim) { + dist[e.to] = dist[cur] + 1; + q.push(e.to); }}} - while (!q.empty()) q.pop(); - return dist[s] >= 0; + return dist[t] >= 0; } bool dfs(int v, ll flow) { - if (flow == 0) return false; if (v == t) return true; - for (; pt[v] < sz(adjlist[v]); pt[v]++) { - int id = adjlist[v][pt[v]], to = edges[id].to; - if (dist[to] == dist[v] + 1 && - edges[id].c - edges[id].f >= flow) { - if (dfs(to, flow)) { - edges[id].f += flow; - edges[id ^ 1].f -= flow; - return true; - }}} + for (; pt[v] < sz(adj[v]); pt[v]++) { + Edge& e = adj[v][pt[v]]; + if (dist[e.to] != dist[v] + 1) continue; + if (e.c - e.f >= flow && dfs(e.to, flow)) { + e.f += flow; + adj[e.to][e.rev].f -= flow; + return true; + }} return false; } ll maxFlow(int source, int target) { - s = source; - t = target; - flow = 0; - dist.resize(sz(adjlist)); - for (lim = (1LL << 62); lim >= 1;) { - if (!bfs()) {lim /= 2; continue;} - pt.assign(sz(adjlist), 0); - while (dfs(s, lim)) flow += lim; - } + s = source, t = target; + ll flow = 0; + for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { + while (bfs(lim)) { + pt.assign(sz(adj), 0); + while (dfs(s, lim)) flow += lim; + }} return flow; } diff --git a/graph/hopcroftKarp.cpp b/graph/hopcroftKarp.cpp index 09d27bc..61ec469 100644 --- a/graph/hopcroftKarp.cpp +++ b/graph/hopcroftKarp.cpp @@ -1,43 +1,47 @@ -vector<vector<int>> adjlist; +vector<vector<int>> adj; // pairs ist der gematchte Knoten oder -1 -vector<int> pairs, dist; +vector<int> pairs, dist, ptr; -bool bfs(int n) { +bool bfs(int l) { queue<int> q; - for(int i = 0; i < n; i++) { + for(int i = 0; i < l; i++) { if (pairs[i] < 0) {dist[i] = 0; q.push(i);} else dist[i] = -1; } + bool exist = false; while(!q.empty()) { int u = q.front(); q.pop(); - for (int v : adjlist[u]) { - if (pairs[v] < 0) return true; + for (int v : adj[u]) { + if (pairs[v] < 0) {exist = true; continue;} if (dist[pairs[v]] < 0) { dist[pairs[v]] = dist[u] + 1; q.push(pairs[v]); }}} - return false; + return exist; } bool dfs(int u) { - for (int v : adjlist[u]) { + for (; ptr[u] < sz(adj[u]); ptr[u]++) { + int v = adj[u][ptr[u]]; if (pairs[v] < 0 || (dist[pairs[v]] > dist[u] && dfs(pairs[v]))) { pairs[v] = u; pairs[u] = v; return true; }} - dist[u] = -1; return false; } -int hopcroft_karp(int n) { // n = #Knoten links +int hopcroft_karp(int l) { // l = #Knoten links int ans = 0; - pairs.assign(sz(adjlist), -1); - dist.resize(n); + pairs.assign(sz(adj), -1); + dist.resize(l); // Greedy Matching, optionale Beschleunigung. - for (int i = 0; i < n; i++) for (int w : adjlist[i]) + for (int i = 0; i < l; i++) for (int w : adj[i]) if (pairs[w] < 0) {pairs[i] = w; pairs[w] = i; ans++; break;} - while(bfs(n)) for(int i = 0; i < n; i++) - if (pairs[i] < 0) ans += dfs(i); + while(bfs(l)) { + ptr.assign(l, 0); + for(int i = 0; i < l; i++) { + if (pairs[i] < 0) ans += dfs(i); + }} return ans; } Binary files differ |