题意：
求最大流
思路：
\(1e5\)条边，偷了一个超长的\(HLPP\)板子。复杂度\(n^2 \sqrt{m}\)。但通常在随机情况下并没有isap快。
板子：
template<class T = int>
struct HLPP{
const int MAXN = 1e5 + 5;
const T INF = 0x3f3f3f3f;
struct edge{
int to, rev;
T f;
};
vector<edge> adj[maxn];
deque<int> lst[maxn];
vector<int> 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<int> 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<int> hlpp;
//hlpp.clear(n)
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <queue>
#define isdigit(a) (a>='0' && a<='9')
typedef long long LL;
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+5;
template<class T = int>
struct HLPP{
const int MAXN = 1e5 + 5;
const T INF = 0x3f3f3f3f;
struct edge{
int to, rev;
T f;
};
vector<edge> adj[maxn];
deque<int> lst[maxn];
vector<int> 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<int> 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<int> 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;
}