题解 P3376 【【模板】网络最大流】

大概是没有人写HLPP(Highest-Label Preflow Push)吧。于是我来写一发。 据说HLPP的复杂度是O(n^2\*√m)，然而常数比较大，又由于本蒟蒻是几个月前写的板子，所以常数大了。 主要思路是： 高度标号：如果一个点的流量溢出了，那么我们需要通过“推流”将它推到适当的地方，所以引导“推流”的方法就是动态的高度标号 重(chong)标号：显然我们不会预先知道标号，然后高度还需正常引导流量，所以我们的Gap函数就是个作用 然而我们的溢出流量并不能一直呆在某个点，所以就要push到周围高度低的点 总之，HLPP的代码量小，细节多，复杂度小，常数大 具体细节在代码里 ```cpp #include <cstdio> #include <cctype> #include <queue> #define INF 0x3f3f3f3f #define MAXN 10010 #define MAXM 300010 using namespace std; inline char get_char(){ static char buf[1000001], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1 ++; } inline int read(){ int num = 0; char c; while (isspace(c = get_char())); while (num = num * 10 + c - 48, isdigit(c = get_char())); return num; } inline int min(int a, int b){ int c = (a - b) >> 31; return (a & c) | (b & ~ c); } int n, m, s, t, tot = 1; int beginx[MAXN], endx[MAXM], nxt[MAXM], res[MAXM]; inline void add_edge(int u, int v, int w){ nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = v, res[tot] = w; nxt[++tot] = beginx[v], beginx[v] = tot, endx[tot] = u, res[tot] = 0; } struct PQ{ int x,h; PQ(int _x,int _h){ x = _x, h = _h; } bool operator < (const PQ &tar) const { return h < tar.h; } }; int gap[MAXN], d[MAXN], ans[MAXN];//gap数组指向当前高度节点个数（相对的，不会实时更新），d数组指向每一个节点的高度，ans模拟每一个节点的流 inline bool push(int x, int y, int ptr) { int w = min(ans[x], res[ptr]);//确定可推流量 res[ptr] -= w, res[ptr^1] += w;//更新反向边 ans[x] -= w, ans[y] += w;//推出溢出 return w; } inline void Gap(int val){ for (int i = 1; i <= n; ++i) if(i != s && i != t && val < d[i] && d[i] <= n) d[i] = n + 1;//检查出=除源点外高度比该点高的点 } inline int HLPP(){ priority_queue<PQ> pq; d[s] = n, ans[s] = INF, pq.push(PQ(s, d[s]));//从起点溢出了无限流量 int u; while(!pq.empty()){ u = pq.top().x, pq.pop(); if(!ans[u]) continue;//不处理没有溢出的流 for(int i = beginx[u], v = endx[i]; i; i = nxt[i], v = endx[i]) if((u == s || d[u] == d[v] + 1) && push(u, v, i) && v != t && v != s) pq.push(PQ(v, d[v]));//如果在源点或者是可以高度推流且允许改变流量且v不是源点或汇点 if (u != s && u != t && ans[u]){//如果当前点不是源点或汇点且已经有流溢出但没有在上一个for循环中推出去 if(!(--gap[d[u]])) Gap(d[u]);//如果当前高度只有一个节点进行Gap操作且等待更新（在提高流量后的下一次出队检查是否可以推出去） ++gap[++d[u]];//提升高度，否则就卡流量了 pq.push(PQ(u, d[u]));//等待处理（看新一轮处理能否把流量推出去） } } return ans[t]; } int main(){ n = read(), m = read(), s = read(), t = read(); for(int i = 1; i <= m; i++){ int u = read(), v = read(), r = read(); add_edge(u, v, r); } printf("%d", HLPP()); return 0; } ```