题解 CF343E 【Pumping Stations】

· · 题解

前置知识：最小割树

已有题解都是使用分治来构造方案的，但其实有一种代码难度更低且时间复杂度更优的贪心 bfs 构造方法，这里给出其步骤及感性证明。

第一问的答案是最小割树的边权之和，我们知道两点的最小割是它们在最小割树上路径上边权的最小值，取相邻点的边权显然最优。

但是这样就有一个问题：答案要求是一个排列，如果最小割树上有某个点的度数 \ge 3，那么与它相连的每个点显然无法同时在排列中与它相邻。

如何处理？答案是显然的：我们会先放边权大的点，再放边权小的点，按照最小割的计算方法，比这条边的边权更大的边权都可以视作与它相等，于是这条边对答案的贡献就是其边权。

这个结论可以拓展到第二问的构造：在优先队列里插入任意一个点作为起点，每次取出堆顶的点并输出，将与其相邻的点及边权都加入优先队列，优先队列以边权为关键字。

如何证明它的正确性？考虑感性反证：定义将某个点 i 加入优先队列的边为 fa_i，如果有某条边对答案的贡献不是它的边权，令这条边中加入的点为 u，排列中在 u 前面一位的点为 v，那么一定有 fa_u 的边权 \le fa_v 的边权 \le 从 \text{lca}(u,v) 到 u 上 fa_u 之外每条边的边权，由于比 fa_u 的边权更大的边权都可以视作与它相等，所以答案并不会减少，矛盾。

时间复杂度 O(n^3m+n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxm=1010,maxn=210;
const ll inf=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
struct edge{
    int to,nxt,f,f_;
}e[maxm<<1];
int hd[maxn],len=1,tmp[maxn];
inline void addedge(int fr,int to,int f){
    e[++len]={to,hd[fr],f,f};
    hd[fr]=len;
    e[++len]={fr,hd[to],f,f};
    hd[to]=len;
}
int n,s,t;
ll dep[maxn];
inline bool bfs1(){
    clear(dep,n);
    dep[s]=1;
    queue<int>q;
    q.push(s);
    while(q.size()){
        ri p=q.front();q.pop();
        for(ri i=hd[p];i;i=e[i].nxt)
            if(e[i].f>0&&!dep[e[i].to])
                dep[e[i].to]=dep[p]+1,q.push(e[i].to);
    }
    return dep[t];
}
ll dfs(int p,ll lim){
    if(p==t)return lim;
    ll sum=0;
    for(ri i=hd[p];i;i=e[i].nxt)
        if(e[i].f>0&&dep[p]+1==dep[e[i].to]){
            ll f=dfs(e[i].to,min(lim-sum,(ll)e[i].f));
            if(f){
                e[i].f-=f,e[i^1].f+=f;
                sum+=f;
                if(sum==lim)break;
            }
        }
    if(!sum)dep[p]=0;
    return sum;
}
inline ll dinic(){
    for(ri i=2;i<=len;++i)e[i].f=e[i].f_;
    ll ret=0;
    while(bfs1()){
        ret+=dfs(s,inf);
        memcpy(hd,tmp,n+1<<1);
    }
    return ret;
}
ll ans;
typedef pair<ll,int> pli;
#define fi first
#define se second
vector<pli>g[maxn];
void build(const vector<int> &v){
    if(v.size()<2)return;
    s=v.front(),t=v.back();
    ll f=dinic();
    ans+=f;
    g[s].emplace_back(f,t),g[t].emplace_back(f,s);
    vector<int>l,r;
    for(ri i:v)(dep[i]?l:r).push_back(i);
    build(l),build(r);
}
bool vis[maxn];
inline void bfs2(){
    priority_queue<pli,vector<pli>,less<pli>>q;
    q.push({0,1});
    while(q.size()){
        ri p=q.top().se;q.pop();
        printf("%d ",p);
        vis[p]=true;
        for(auto &i:g[p])
            if(!vis[i.se])
                q.push(i);
    }
}
int m,q,t_case;
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        ri x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    memcpy(tmp,hd,n+1<<1);
    vector<int>v;
    for(ri i=1;i<=n;++i)v.push_back(i);
    build(v);
    printf("%lld\n",ans);
    bfs2();
    return 0;
}