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

皎月半洒花

2019-02-14 03:21:22

Solution

其实类似的思路已经有大佬提过了,我在此再赘述一翻的原因是我主要想讲一些算法的理解向问题。 朴素的$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)}}$