题解 P4722 【【模板】最大流 加强版 / 预流推进】
皎月半洒花
2019-02-14 03:21:22
其实类似的思路已经有大佬提过了,我在此再赘述一翻的原因是我主要想讲一些算法的理解向问题。
朴素的$HLPP$是基于$Gap + Heap$的,是一个复杂度较为优秀、但是有不够优秀的算法,详情可以见[$Link$](http://www.orchidany.cf/2019/01/11/HLPP)。
我们直接上优化
我们首先思考思考普通的HLPP到底会慢在哪里:
* $STL$支持的$heap$(比如优先队列)实在是太太太…太慢了!
* 每次$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):
```cpp
//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$
```cpp
#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) ;
}
```
## $\bold{\mathfrak{writter:Orchidany(pks)}}$