题解归档 - cf343E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf343E
• 本地来源：problems/cf343E/idea.md
• 题目链接：https://codeforces.com/contest/343/problem/E
• 原始标题：CF343E Pumping Stations

思路

CF343E Pumping Stations

题意

$n$ 个站点、$m$ 条无向边（容量为带宽）。要选排列 $v_1,\ldots,v_n$，依次在 $v_i\to v_{i+1}$ 上泵送，第 $i$ 天收益为从 $v_i$ 流出的总流量（等于该点对最大流）。求最大总收益及任一最优排列。

做法

1. Gomory-Hu 树：任意两点最大流等于 GH 树上路径最小边权；最优总收益 = GH 树所有边权之和。
2. 建树：SAP/Dinic 求 $n-1$ 次最大流，按标准 GH 合并规则维护 fa[]、val[]。
3. 构造排列：在 GH 树上递归取当前子树最小边 $(pu,pv)$ 分割，左右子树分别递归得到链，调整方向后拼接。

复杂度

$O(n\cdot \text{maxflow})$，$n\le 200$ 可过。

本地验证

样例 77；小 $n$ 可与 brute.cpp 对拍。

代码

来源：problems/cf343E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 07:32:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=205,INF=1e18;
struct edge{ll to,cap,rev;};
vector<edge>g[maxn],og[maxn];
ll n,m,i,j,k,u,v,ss,tt,flow,sum,pu,pv,mi;
ll a[maxn],b[maxn],c[maxn],level[maxn],curp[maxn],cutv[maxn],fa[maxn],val[maxn],side[maxn];
void add(ll x,ll y,ll cap){
    g[x].push_back({y,cap,(ll)g[y].size()});
    g[y].push_back({x,0,(ll)g[x].size()-1});
}
void rebuild(){
    ll i;
    for(i=0;i<=n;i++) g[i]=og[i];
}
bool bfs(){
    ll i,h=0,tl=1,q[maxn+5];
    for(i=0;i<=n;i++) level[i]=-1,curp[i]=0;
    level[ss]=0,q[0]=ss;
    while(h<tl){
        u=q[h++];
        for(i=0;i<(ll)g[u].size();i++){
            edge e=g[u][i];
            if(e.cap>0 and level[e.to]==-1){
                level[e.to]=level[u]+1;
                q[tl++]=e.to;
            }
        }
    }
    return level[tt]!=-1;
}
ll dfs(ll u,ll aug){
    ll i,v,fl=0;
    if(u==tt) return aug;
    for(i=curp[u];i<(ll)g[u].size();i++){
        curp[u]=i;
        edge e=g[u][i];
        if(e.cap>0 and level[e.to]==level[u]+1){
            v=dfs(e.to,min(aug,e.cap));
            if(v>0){
                g[u][i].cap-=v;
                g[e.to][e.rev].cap+=v;
                fl+=v;
                aug-=v;
                if(aug==0) break;
            }
        }
    }
    return fl;
}
ll dinic(){
    ll zc=0,aug;
    while(bfs()){
        while((aug=dfs(ss,INF))>0) zc+=aug;
    }
    return zc;
}
void mark_cut(){
    ll i,h=0,tl=1,q[maxn+5];
    for(i=1;i<=n;i++) cutv[i]=0;
    cutv[ss]=1,q[0]=ss;
    while(h<tl){
        u=q[h++];
        for(i=0;i<(ll)g[u].size();i++){
            edge e=g[u][i];
            if(e.cap>0 and !cutv[e.to]){
                cutv[e.to]=1;
                q[tl++]=e.to;
            }
        }
    }
}
void build_gh(){
    for(i=1;i<=n;i++) fa[i]=1,val[i]=0;
    for(u=2;u<=n;u++){
        v=fa[u];
        rebuild();
        ss=u,tt=v;
        flow=dinic();
        mark_cut();
        for(i=1;i<=n;i++)
            if(i!=u and fa[i]==v and cutv[i]) fa[i]=u;
        if(cutv[fa[v]]){
            fa[u]=fa[v],val[u]=val[v];
            fa[v]=u,val[v]=flow;
        }else val[u]=flow;
    }
    sum=0;
    for(i=2;i<=n;i++) sum+=val[i];
}
ll in_nodes(const vector<ll>&verts,ll x){
    ll i;
    for(i=0;i<(ll)verts.size();i++) if(verts[i]==x) return 1;
    return 0;
}
void find_min(const vector<ll>&verts){
    ll i,u,v,w;
    mi=INF;
    for(i=0;i<(ll)verts.size();i++){
        u=verts[i];
        if(u==1) continue;
        v=fa[u];
        if(!in_nodes(verts,v)) continue;
        w=val[u];
        if(w<mi) mi=w,pu=v,pv=u;
    }
}
void side_dfs(ll x,ll ff,const vector<ll>&verts){
    ll i,y;
    side[x]=1;
    for(i=0;i<(ll)verts.size();i++){
        y=verts[i];
        if(y==x or y==ff or side[y]) continue;
        if((x==pu and y==pv) or (x==pv and y==pu)) continue;
        if(fa[y]==x or fa[x]==y) side_dfs(y,x,verts);
    }
}
vector<ll>build_path(vector<ll>verts){
    ll i;
    vector<ll>left,right,out,r;
    if(verts.size()<=1) return verts;
    find_min(verts);
    for(i=0;i<=n;i++) side[i]=0;
    side_dfs(pu,0,verts);
    for(i=0;i<(ll)verts.size();i++){
        if(side[verts[i]]) left.push_back(verts[i]);
        else right.push_back(verts[i]);
    }
    if(left.empty() or right.empty()) return verts;
    out=build_path(left);
    r=build_path(right);
    if(out.back()!=pu) reverse(out.begin(),out.end());
    if(r.front()!=pv) reverse(r.begin(),r.end());
    out.insert(out.end(),r.begin(),r.end());
    return out;
}
int main(){
    vector<ll>verts,ord;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i];
        add(a[i],b[i],c[i]);
        add(b[i],a[i],c[i]);
    }
    for(i=0;i<=n;i++) og[i]=g[i];
    build_gh();
    cout<<sum<<"\n";
    for(i=1;i<=n;i++) verts.push_back(i);
    ord=build_path(verts);
    for(i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<ord[i];
    }
    cout<<"\n";
    return 0;
}