题意：
求最大流
思路：
\(1e5\)条边，偷了一个超长的\(HLPP\)板子。复杂度\(n^2 \sqrt{m}\)。但通常在随机情况下并没有isap快。
板子：
templatestruct HLPP{ const int MAXN = 1e5 + 5; const T INF = 0x3f3f3f3f; struct edge{ int to, rev; T f; }; vector adj[maxn]; deque lst[maxn]; vector gap[maxn]; T excess[maxn]; int highest, height[maxn], cnt[maxn], ptr[maxn], work, N; void addEdge(int u, int v, int f, bool isdirected = true){ adj[u].push_back({v, adj[v].size(), f}); adj[v].push_back({u, adj[u].size() - 1, isdirected? 0 : f}); } void clear(int n){ N = n; for(int i = 0; i <= n; i++){ adj[i].clear(), lst[i].clear(); gap[i].clear(); } } void upHeight(int v, int nh){ ++work; if(height[v] != N) --cnt[height[v]]; height[v] = nh; if(nh == N) return; cnt[nh]++, highest = nh; gap[nh].push_back(v); if(excess[v] > 0){ lst[nh].push_back(v); ++ptr[nh]; } } void glovalRelabel(int s, int t){ work = 0; fill(height, height + N + 1, N); fill(cnt, cnt + N + 1, 0); for(int i = 0; i <= highest; i++){ lst[i].clear(); gap[i].clear(); ptr[i] = 0; } height[t] = 0; queue q({t}); while(!q.empty()){ int v = q.front(); q.pop(); for(auto &e : adj[v]) if(height[e.to] == N && adj[e.to][e.rev].f > 0){ q.push(e.to); upHeight(e.to, height[v] + 1); } highest = height[v]; } } void push(int v, edge& e){ if(excess[e.to] == 0){ lst[height[e.to]].push_back(e.to); ++ptr[height[e.to]]; } T df = min(excess[v], e.f); e.f -= df; adj[e.to][e.rev].f += df; excess[v] -= df; excess[e.to] += df; } void discharge(int v){ int nh = N; for(auto &e : adj[v]){ if(e.f > 0){ if(height[v] == height[e.to] + 1){ push(v, e); if(excess[v] <= 0) return; } else{ nh = min(nh, height[e.to] + 1); } } } if(cnt[height[v]] > 1){ upHeight(v, nh); } else{ for(int i = height[v]; i < N; i++){ for(auto j : gap[i]) upHeight(j, N); gap[i].clear(); ptr[i] = 0; } } } T hlpp(int s, int t){ fill(excess, excess + N + 1, 0); excess[s] = INF, excess[t] = -INF; glovalRelabel(s, t); for(auto &e : adj[s]) push(s, e); for(; highest >= 0; -- highest){ while(lst[highest].size()){ int v = lst[highest].back(); lst[highest].pop_back(); discharge(v); if(work > 4 * N) glovalRelabel(s, t); } } return excess[t] + INF; }};int read() { int f = 1, x = 0; char ch = getchar(); while(! isdigit(ch)) {if(ch == '-' ) f = -f; ch = getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();} return x * f;}HLPP hlpp;//hlpp.clear(n)
代码：
#include#include #include #include #include #include #include #define isdigit(a) (a>='0' && a<='9')typedef long long LL;using namespace std;const int inf = 0x3f3f3f3f;const int maxn = 2e5+5;template struct HLPP{ const int MAXN = 1e5 + 5; const T INF = 0x3f3f3f3f; struct edge{ int to, rev; T f; }; vector adj[maxn]; deque lst[maxn]; vector gap[maxn]; T excess[maxn]; int highest, height[maxn], cnt[maxn], ptr[maxn], work, N; void addEdge(int u, int v, int f, bool isdirected = true){ adj[u].push_back({v, adj[v].size(), f}); adj[v].push_back({u, adj[u].size() - 1, isdirected? 0 : f}); } void clear(int n){ N = n; for(int i = 0; i <= n; i++){ adj[i].clear(), lst[i].clear(); gap[i].clear(); } } void upHeight(int v, int nh){ ++work; if(height[v] != N) --cnt[height[v]]; height[v] = nh; if(nh == N) return; cnt[nh]++, highest = nh; gap[nh].push_back(v); if(excess[v] > 0){ lst[nh].push_back(v); ++ptr[nh]; } } void glovalRelabel(int s, int t){ work = 0; fill(height, height + N + 1, N); fill(cnt, cnt + N + 1, 0); for(int i = 0; i <= highest; i++){ lst[i].clear(); gap[i].clear(); ptr[i] = 0; } height[t] = 0; queue q({t}); while(!q.empty()){ int v = q.front(); q.pop(); for(auto &e : adj[v]) if(height[e.to] == N && adj[e.to][e.rev].f > 0){ q.push(e.to); upHeight(e.to, height[v] + 1); } highest = height[v]; } } void push(int v, edge& e){ if(excess[e.to] == 0){ lst[height[e.to]].push_back(e.to); ++ptr[height[e.to]]; } T df = min(excess[v], e.f); e.f -= df; adj[e.to][e.rev].f += df; excess[v] -= df; excess[e.to] += df; } void discharge(int v){ int nh = N; for(auto &e : adj[v]){ if(e.f > 0){ if(height[v] == height[e.to] + 1){ push(v, e); if(excess[v] <= 0) return; } else{ nh = min(nh, height[e.to] + 1); } } } if(cnt[height[v]] > 1){ upHeight(v, nh); } else{ for(int i = height[v]; i < N; i++){ for(auto j : gap[i]) upHeight(j, N); gap[i].clear(); ptr[i] = 0; } } } T hlpp(int s, int t){ fill(excess, excess + N + 1, 0); excess[s] = INF, excess[t] = -INF; glovalRelabel(s, t); for(auto &e : adj[s]) push(s, e); for(; highest >= 0; -- highest){ while(lst[highest].size()){ int v = lst[highest].back(); lst[highest].pop_back(); discharge(v); if(work > 4 * N) glovalRelabel(s, t); } } return excess[t] + INF; }};int read() { int f = 1, x = 0; char ch = getchar(); while(! isdigit(ch)) {if(ch == '-' ) f = -f; ch = getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();} return x * f;}HLPP hlpp;int main() { int T; scanf("%d", &T); while(T--) { int n, m; scanf("%d%d", &n, &m); int x, y, s, t; int startX = inf, endX = -inf; for(int i = 1; i <= n; ++i) { x = read(), y = read(); if(x < startX) s = i, startX = x; if(x > endX) t = i, endX = x; } int u, v, f; hlpp.clear(n); for(int i = 1; i <= m; ++i) { u = read(), v = read(), f = read(); hlpp.addEdge(u, v, f, false); } printf("%d\n", hlpp.hlpp(s, t)); } return 0;}