题解 P4722 【【模板】最大流加强版 / 预流推进】

皎月半洒花 · 2019-02-14 03:21:22 · 题解

其实类似的思路已经有大佬提过了，我在此再赘述一翻的原因是我主要想讲一些算法的理解向问题。

朴素的HLPP是基于Gap + Heap的，是一个复杂度较为优秀、但是有不够优秀的算法，详情可以见Link。

我们直接上优化

我们首先思考思考普通的HLPP到底会慢在哪里：

每次Gap优化，我们的时间复杂度是紧确的\Theta(n)。的这显然不合算，因为假设我当前的\bold{gap}（断层）正好位于倒数第一高的点和倒数第二高的点，那么也就相当于我单次会浪费\bold{\Theta(n)}的时间。

事实上…普通的HLPP代码并不长，主要问题就是这两个。

我们考虑，如果不用堆的话怎么做呢？

呃…不用堆的意思并不是我们不从高度最大的点开始推送。这个地方需要一个idea——在HLPP中，高度函数\bold{H(x)}和点数集大小\bold{N(x)}是广义同阶的。 换句话说，我们可以考虑从高度入手。

换句话说，我们原来是通过节点编号访问节点以及其高度，现在我们如果从高度入手，再去访问节点，我们就可以做到\bold{O(n)}而不是\bold{\rm{O(nlogn)}} 。那么由于同一高度的节点或许有很多，直接开一个vector。在这个地方我们用vector而不用二维数组建立二维关系的原因，主要是我们初始化麻烦得很，如果套用memset或者fill的话，常数之大可想而知。

那么这两个问题就顺理成章地解决了。但这个地方还有一个优化，就是虽然vector和list都是线性容器，但是list的本质是双向链表，频繁处理插入删除操作时会具有更优秀的表现。

也就是说，原来的Gap数组我们可以直接用list做，以图更小的常数。那么这时存在一个问题，就是虽然本质上删除是容易的，但是你怎么知道要删同一高度下的哪个元素(=@__@=)？就算你知道，list也不知道啊2333

hhh不皮了，其实我们记录一下位置就好，即记录一下每个节点在list中的位置，单独开一个Iterator类型的vector记录即可。

好了，现在我们获得了10倍+的常数优势qwq，撒花花…

哦对，还有几点我debug的时候被坑死的点：

那个Iterator类型的vector对象是点的编号不是高度！
注意你的下标！下标！再说一遍，下标！因为STL自带左闭右开的性质~~wrnm~~，所以一定要注意，如果你是[1,n]选手，注意你的assign函数！

\color{red}{C}\color{cyan}{o}\color{gold}{d}\color{green}{e}·2 (我觉得写的很难看但是有注释qaq)：

//writter:Orchidany(pks)
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")//sb毒瘤优化

#define MAXN 10030
#define min my_min
#define BG begin()
#define gc getchar
#define rr register 
#define Iter iterator
#define INF 2147483647
#define rep(i, a, x) for(i = a ; i <= x ; ++ i)

using namespace std ;
typedef list<int> List ; int step;

struct Edge{
    int to, f, next ;
    Edge(int to,int f,int next):to(to),f(f),next(next){}//没有人发现正下方这句注释前半句和后半句都是三个音节的吗qaq
} ; vector <int> q, H, Extra, Set[MAXN], cnt ; List Gap[MAXN] ;//list，就是快（
//q:队列，H:高度，Extra：每个点的超额流，Set:…就是那个经典版HLPP里的堆，高度做第一维
int Ans, N, M, S, T, max_H, now_H ; vector <Edge> E[MAXN] ; /*vector存边（据说会快）*/vector<List::iterator> Era_pos ; //辅助定位+删除

inline void eggs() { ;}//for free~
inline int my_min(int a, int b){return a & ((a - b) >> 31) | b & ( ~ (a - b) >> 31) ;}//黑科技
inline void Add(int f, int v, int u){ E[u].push_back(Edge(v, f, E[v].size())), E[v].push_back(Edge(u, 0, E[u].size() - 1)) ; }
inline int qr(){ rr int k = 0 ; char c = gc() ; while (!isdigit(c)) c = gc() ;while (isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = gc() ; return k ; }

inline void Init_label(){//等价于一开始的那个BFS，只执行一次
    rr int i, h = 0, t = 0 ;q.clear(), q.resize(N) ; 
    H.assign(N + 1, N + 1) ; H[T] = 0 ; q[t ++] = T ;//从T（高度小的）向前标号
    while (h < t){//队列……BFS……真熟悉啊……嗝……
        rr int now = q[h] ; ++ h ;
        for (vector <Edge> :: Iter k = E[now].begin() ; k != E[now].end() ; ++ k)
            if (H[k->to] == N + 1 && E[k->to][k->next].f) H[k->to] = H[now] + 1, ++ cnt[H[k->to]], q[t ++] = k->to ;
    }
    rep(i, 0, N + 1) Set[i].clear(), Gap[i].clear() ;//还是清空一下比较好吧
    rep(i, 0, N) 
        if (H[i]  <N + 1)  
            Era_pos[i] = Gap[H[i]].insert(Gap[H[i]].BG, i), //疑似insert函数的返回值是一个指针qaq
            (Extra[i]>0) ? Set[H[i]].push_back(i) : eggs() ;//这个彩蛋（eggs）是因为，三目运算符":"两边类型需要形同…
    max_H = now_H = H[q[-- t]] ; //更新，BFS的性质，最后一个元素一定高度最大（除了源点）
}
inline void Push(int x, Edge &e){//单独写出来的push函数，好像很方便？
    rr int now_flow = min(Extra[x], e.f) ;
    Extra[x] -= now_flow, e.f -= now_flow, Extra[e.to] += now_flow, E[e.to][e.next].f += now_flow ;
    if (Extra[e.to] > 0 && Extra[e.to] <= now_flow) Set[H[e.to]].push_back(e.to) ;  // push it into "heap"
}
inline void _Push(int x){
    rr int i, x_h = N, t = H[x] ; 
    for (vector <Edge> :: Iter k = E[x].BG ; k != E[x].end() ; ++ k)
        if (k->f > 0)//如果可以流
            if (H[k->to] == H[x] - 1) { Push(x, *k) ; if (!Extra[x]) return ;} else x_h = min(x_h, H[k->to] + 1) ;
    if (cnt[H[x]] <= 1){//如果出现断层了
        for(i = t ; i <= max_H ; Gap[i].clear(), ++ i)//这个gap的for肯定比O(n)优秀
            for(List::Iter k = Gap[i].BG ; k != Gap[i].end() ; ++ k) cnt[H[*k]] --, H[*k] = N ; 
        max_H = t - 1 ; /*断层以上的高度都没用了*/return ;
    }
    -- cnt[t], Era_pos[x] = Gap[t].erase(Era_pos[x]) ; H[x] = x_h ; if (x_h == N) return ; //重贴标签操作，为当前点删除原来的高度
    ++ cnt[x_h], Era_pos[x] = Gap[x_h].insert(Gap[x_h].begin(), x), max_H = max(now_H = x_h, max_H), Set[x_h].push_back(x) ;//增添新的高度
}
inline int HLPP(){
    rr int i, now ; H.assign(N, 0) ; H[S] = N ; Era_pos.resize(N)  ;
    rep(i, 0, N - 1) if (i != S) Era_pos[i] = Gap[H[i]].insert(Gap[H[i]].BG, i) ; 
    cnt.assign(N, 0), cnt[0] = N - 1 ; Extra.assign(N, 0), Extra[S] = INF, Extra[T] =- INF ;
    rep(i, 0, E[S].size() - 1) Push(S, E[S][i]) ;  //下面源点要单独拿出来推送，因为源点推送时高度差不需要=1.
    Init_label() ; //初始化（BFS）
    while (now_H >= 0) //正式开始HLPP（泪目）
        if (Set[now_H].empty()) now_H -- ; //高度递减，实现一个堆的效果
        else now = Set[now_H].back(), Set[now_H].pop_back(), _Push(now) ;
    return Extra[T] + INF ;
}
int main(){
    N = qr(),; rr int i ;//下面的++N是为了日后好操作qaq
    rep(i, 1, M) Add(qr(), qr(), qr()) ; ++ N, Ans = HLPP() ; cout << Ans << endl ; return 0 ; 
}

下面是个fread卡常版本qaq

#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")

#define MAXN 1202
#define min my_min
#define BG begin()
#define rr register
#define swap my_swap 
#define Iter iterator
#define INF 2147483647
#define rep(i, a, x) for(i = a ; i <= x ; ++ i)

using namespace std ;
typedef list<int> List ; int step;
const int ch_top=4e7+3;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;

inline int read(){
    while(*++now_r<'0');
    register int x=*now_r-'0';
    while(*++now_r>='0')x=x*10+*now_r-'0';
    return x;
}
inline void write(int x){
    static char st[20];static int top;
    while(st[++top]='0'+x%10,x/=10);
    while(*++now_w=st[top],--top);
    *++now_w='\n';
}

struct Edge{
    int to, f, next ;
    Edge(int to,int f,int next):to(to),f(f),next(next){}
} ; vector <int> q, H, Extra, Set[MAXN], cnt ; List Gap[MAXN] ;
int Ans, N, M, S, T, max_H, now_H ; vector <Edge> E[MAXN] ; vector<List::iterator> Era_pos ; 

inline void eggs() { ;}//for free~
inline int my_min(int a, int b){return a & ((a - b) >> 31) | b & ( ~ (a - b) >> 31) ;}
inline void Add(int f, int v, int u){ E[u].push_back(Edge(v, f, E[v].size())), E[v].push_back(Edge(u, 0, E[u].size() - 1)) ; }

inline void Init_label(){
    rr int i, h = 0, t = 0 ;q.clear(), q.resize(N) ; 
    rr int qaq = N + 1 ; H.assign(qaq, qaq) ; H[T] = 0 ; q[t ++] = T ;
    while (h < t){
        rr int now = q[h], qwq = H[now] + 1 ; ++ h ; 
        for (vector <Edge> :: Iter k = E[now].begin() ; k != E[now].end() ; ++ k)
            if (H[k->to] == qaq && E[k->to][k->next].f) H[k->to] = qwq, ++ cnt[H[k->to]], q[t ++] = k->to ;
    }
    rep(i, 0, N - 1) Set[i].clear(), Gap[i].clear() ;
    rep(i, 0, N - 1) if (H[i] < N)  Era_pos[i] = Gap[H[i]].insert(Gap[H[i]].BG, i), (Extra[i] > 0) ? Set[H[i]].push_back(i) : eggs() ;
    max_H = now_H = H[q[-- t]] ; 
}
inline void Push(int x, Edge &e){
    rr int now_flow = min(Extra[x], e.f) ;
    Extra[x] -= now_flow, e.f -= now_flow, Extra[e.to] += now_flow, E[e.to][e.next].f += now_flow ;
    if (Extra[e.to] > 0 && Extra[e.to] <= now_flow) Set[H[e.to]].push_back(e.to) ;  // push it into heap
}
inline void _Push(int x){
    rr int i, x_h = N, t = H[x] ; 
    for (vector <Edge> :: Iter k = E[x].BG ; k != E[x].end() ; ++ k)
        if (k->f > 0)
            if (H[k->to] == H[x] - 1) { Push(x, *k) ; if (!Extra[x]) return ;} else x_h = min(x_h, H[k->to] + 1) ;
    if (cnt[H[x]] <= 1){
        for(i = t ; i <= max_H ; Gap[i].clear(), ++ i)
            for(List::Iter k = Gap[i].BG ; k != Gap[i].end() ; ++ k) cnt[H[*k]] --, H[*k] = N ; max_H = t - 1 ; return ;
    }
    -- cnt[t], Era_pos[x] = Gap[t].erase(Era_pos[x]) ; H[x] = x_h ; if (x_h == N) return ; 
    ++ cnt[x_h], Era_pos[x] = Gap[x_h].insert(Gap[x_h].begin(), x), max_H = max(now_H = x_h, max_H), Set[x_h].push_back(x) ;
}
int HLPP(){
    rr int i, now ; H.assign(N, 0) ; H[S] = N ; cnt.assign(N, 0) ; Era_pos.resize(N) ;
    rep(i, 0, N - 1) if (i != S) Era_pos[i] = Gap[H[i]].insert(Gap[H[i]].BG, i) ; cnt[0] = N - 1 ;
    Extra.assign(N, 0), Extra[S] = INF, Extra[T] = -INF ; rep(i, 0, E[S].size() - 1) Push(S, E[S][i]) ;  Init_label() ; 
    while (now_H >= 0) if (Set[now_H].empty()) now_H -- ; else now = Set[now_H].back(), Set[now_H].pop_back(), _Push(now) ;return Extra[T] + INF ;
}
int main(){
    fread(ch,1,ch_top,stdin); N = read(), M = read(), S = read(), T = read() ; rr int i ;
    rep(i, 1, M) Add(read(), read(), read()) ; ++ N, Ans = HLPP() ; write(Ans) ; fwrite(ch,1,now_w-ch,stdout) ;
}

题解 P4722 【【模板】最大流 加强版 / 预流推进】

\color{red}{C}\color{cyan}{o}\color{gold}{d}\color{green}{e}·2 (我觉得写的很难看但是有注释qaq)：

\bold{\mathfrak{writter:Orchidany(pks)}}

题解 P4722 【【模板】最大流加强版 / 预流推进】