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

· · 题解

Dinic 算法的超级优化版。

用第一篇题解的代码与 LOJ 上的数据调了好久。

因为我认为他们的码风不太好。

所以看了一下午。

普通 Dinic

只能过 16 pts。

注意，当前弧优化其实对于 Dinic 不是优化，而是保证 O(n^2m) 时间复杂度的一部分。

//Dinic 算法  
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[10010],to[240010],nxt[240010],val[240010],tot=1;
void add(int u,int v,int w){
    to[++tot]=v,val[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
int maxflow,dis[10010],now[10010];
bool vis[10010];
bool bfs(){
    queue<int>q;
    memset(vis,0,sizeof vis);
    vis[s]=1,dis[s]=0,now[s]=head[s];
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]){
            if(vis[to[i]] || !val[i]) continue;
            now[to[i]]=head[to[i]];
            dis[to[i]]=dis[u]+1,vis[to[i]]=1;
            q.push(to[i]);
            if(to[i]==t) return 1;
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow;
    for(int i=now[x];i && rest;i=nxt[i]){
        now[x]=i;
        if(dis[to[i]]!=dis[x]+1 || !val[i]) continue;
        int v=dinic(to[i],min(rest,val[i]));
        if(!v) dis[to[i]]=0;
        val[i]-=v,val[i^1]+=v;
        rest-=v;
    }
    return flow-rest;
}
signed main() {
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w),add(v,u,0);
    }
    int flow=0;
    while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
    cout<<maxflow;
    return 0;
}

优化 1，按位分段

Dinic 算法在流量差异大的时候跑的慢。

所以，可以将流量按二进制位分段。

将所有 2^p \le x < 2^{p+1} 分为一组。

从大到小枚举组，去跑 Dinic。

将每次跑组跑完的边留下来，放到下一组接着跑。

这样时间复杂度能大大降低。

看代码。

//Dinic 算法  
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[10010],to[240010],nxt[240010],val[240010],tot=1;
void add(int u,int v,int w){
    to[++tot]=v,val[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
int maxflow,dis[10010],now[10010];
bool vis[10010];
bool bfs(){//BFS 分层 
    queue<int>q;//STL 队列 
    memset(vis,0,sizeof vis);
    vis[s]=1,dis[s]=0,now[s]=head[s];
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]){
            if(vis[to[i]] || !val[i]) continue;
            now[to[i]]=head[to[i]];
            dis[to[i]]=dis[u]+1,vis[to[i]]=1;
            q.push(to[i]);
            if(to[i]==t) return 1;//有增广路，直接 return
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow;
    for(int i=now[x];i && rest;i=nxt[i]){
        now[x]=i;//当前弧优化
        if(dis[to[i]]!=dis[x]+1 || !val[i]) continue;
        int v=dinic(to[i],min(rest,val[i]));
        if(!v) dis[to[i]]=0;
        val[i]-=v,val[i^1]+=v;
        rest-=v;
    }
    return flow-rest;
}
struct node{
    int u,v,w;
}e[120010];
signed main() {
    ios::sync_with_stdio(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;//存边
    for(int i=30;i>=0;i--){//枚举位
        int p=(1<<i);
        for(int j=1;j<=m;j++) if(e[j].w>=p && e[j].w<p*2) add(e[j].u,e[j].v,e[j].w),add(e[j].v,e[j].u,0);//枚举边并加入，注意反向边
        int flow=0;//跑 Dinic 并统计答案
        while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;//不删边，留到下一组接着跑
    } 
    cout<<maxflow;
    return 0;
}

有 68 pts。

优化 2，反向滞留

这我自己取的名字。

你看，上一个优化都可以先跑一部分的图。

那这也可以。

发现反向边有点影响效率（人家跑过来的，你跑回去）。

于是先不算反向边跑一边 Dinic，但计算反向边的权值。

跑完后，直接加上反向边，再跑一次 Dinic。

发现效率大大提升。

代码。

//Dinic 算法  
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[10010],to[240010],nxt[240010],val[240010],tot=1;
vector<int>e[10010];
void add(int u,int v,int w){//注意 add 函数有变化
    to[++tot]=v,val[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
    e[u].push_back(tot);//这里存的是要去跑 Dinic 的边 
    to[++tot]=u,val[tot]=0;
    nxt[tot]=head[v];
    head[v]=tot;//反向边先不参与 Dinic，但参与更新
}
int maxflow,dis[10010],now[10010];
bitset<10010>vis;
bool Flag=0;
int Q[10010],H,T;
inline bool bfs(){
    H=1,T=0;
    for(int i=1;i<=n;i++) vis[i]=0;
    vis[s]=1,dis[s]=0,now[s]=0;
    Q[++T]=s;
    while(H<=T){
        int u=Q[H++];
        for(int i=0;i<e[u].size();i++){
            if(vis[to[e[u][i]]] || !val[e[u][i]]) continue;
            now[to[e[u][i]]]=0;
            dis[to[e[u][i]]]=dis[u]+1,vis[to[e[u][i]]]=1;
            Q[++T]=to[e[u][i]];
            if(to[e[u][i]]==t) return 1;
        }
    }
    return 0; 
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow;
    for(int i=now[x];i<e[x].size() && rest;i++){
        now[x]=i;
        if(dis[to[e[x][i]]]!=dis[x]+1 || !val[e[x][i]]) continue;
        int v=dinic(to[e[x][i]],min(rest,val[e[x][i]]));
        if(!v) dis[to[e[x][i]]]=0;
        val[e[x][i]]-=v,val[e[x][i]^1]+=v;
        rest-=v;
    }
    return flow-rest;
}
struct node{
    int u,v,w;
}E[120010];
signed main() {
    ios::sync_with_stdio(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;
    for(int i=30;i>=0;i--){//下面与上面很不一样 
        int p=(1<<i);
        int kt=tot;
        for(int j=1;j<=m;j++)
            if(E[j].w>=p && E[j].w<p*2)
                add(E[j].u,E[j].v,E[j].w);//存边 
        int flow=0;//跑 Dinic 
        while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
        for(int j=1;j<=m;j++){//加反向边
            if(E[j].w>=p && E[j].w<p*2){
                kt+=2;
                e[E[j].v].push_back(kt);
            }
        }
        while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;//再跑一次 
    } 
    cout<<maxflow;
    return 0;
}

有 84 pts。

优化 3，对优化 1 的优化（压位优化）

将每次枚举一个二进制位变成三个二进制位，这样效率也许会高一些。

因为枚举次数会少，但是 Dinic 的值域增加。

所以效率因数据而定。

反正这样是过了。

代码。

//Dinic 算法  
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[1210],to[240010],nxt[240010],val[240010],tot=1;
vector<int>e[1210];
void add(int u,int v,int w){
    to[++tot]=v,val[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
    e[u].push_back(tot);
//  cout<<to[e[u][e[u].size()-1]]<<" "<<w<<"\n";
    to[++tot]=u,val[tot]=0;
    nxt[tot]=head[v];
    head[v]=tot;
}
int maxflow,dis[1210],now[1210];
bitset<1210>vis;
bool Flag=0;
int Q[1210],H,T;
inline bool bfs(){
    H=1,T=0;
    for(int i=1;i<=n;i++) vis[i]=0;
    vis[s]=1,dis[s]=0,now[s]=0;
    Q[++T]=s;
    while(H<=T){
        int u=Q[H++];
        for(int i=0;i<e[u].size();i++){
            if(vis[to[e[u][i]]] || !val[e[u][i]]) continue;
            now[to[e[u][i]]]=0;
            dis[to[e[u][i]]]=dis[u]+1,vis[to[e[u][i]]]=1;
            Q[++T]=to[e[u][i]];
            if(to[e[u][i]]==t) return 1;
        }
    }
    return 0; 
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow;
    for(int i=now[x];i<e[x].size() && rest;i++){
        now[x]=i;
        if(dis[to[e[x][i]]]!=dis[x]+1 || !val[e[x][i]]) continue;
        int v=dinic(to[e[x][i]],min(rest,val[e[x][i]]));
        if(!v) dis[to[e[x][i]]]=0;
        val[e[x][i]]-=v,val[e[x][i]^1]+=v;
        rest-=v;
    }
    return flow-rest;
}
struct node{
    int u,v,w;
}E[120010];
signed main() {
    ios::sync_with_stdio(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;
    for(int i=30;i>=0;i-=3){//3位一次枚举
        int p=(1<<i);
        int kt=tot;
        for(int j=1;j<=m;j++)
            if(E[j].w>=p && E[j].w<p*8)//3位一次枚举
                add(E[j].u,E[j].v,E[j].w);
        int flow=0;
        while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
        for(int j=1;j<=m;j++){
            if(E[j].w>=p && E[j].w<p*8){//3位一次枚举
                kt+=2;
                e[E[j].v].push_back(kt);
            }
        }
        while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
    } 
    cout<<maxflow;
    return 0;
}

AC 记录。

时间复杂度玄学。

总结

像 Dinic 这样的玄学算法，优化是无止境的。

所以我们有时去优化了算法，说不定就能卡过高级的模板题。

就比如说 SPFA 的 SLF 优化（LLL 就不提了，负优化太重）。

还比如 Dinic 的两种优化。

你说，用什么 HLPP。

这几种优化我认为挺实用的。

可以在考场上打（不长）。

平时水题用也可以。