「题解」「CF343E」Pumping Stations

最小割树 简单题。

题目链接：CodeForces 343E。

题目

题目描述

一张 $n$ 个点 $m$ 条边的带权无向图。构造一个排列，求
$$\max\{\sum^n _ {i=2}\operatorname{mincut}(a _ {i-1},a _ i)\}$$

其中 $\operatorname{mincut}(s,t)$ 表示 $s$ 到 $t$ 的最小割。

求答案，并输出构造的排列。

数据范围

变量	数据范围
$n$	$2\leq n\leq 200$
$m$	$1\leq n\leq 1000$
边权	$\leq 100$

时空限制

题目编号	时间限制	空间限制
CodeForces 343E	$2\text{s}$	$256\text{MiB}$

题解

思路

先列出结论，下面再证明。

结论：答案是最小割树上的边权和。构造时将最小割树每次沿边权最小的边割开，递归求解，最后合并。

证明

证明构造方法的正确性。

不妨设当前树的最小边权为 $d$，这条边会将最小割树分为两个连通块 $P,Q$。

设 $u _ 1,v _ 1\in P,u _ 2,v _ 2\in Q$，那么我们来讨论顺序问题。

1. 顺序为 $u _ 1,v _ 1,u _ 2,v _ 2$，即先在两个连通块内，最后合并。
   由最小割树的性质：两点间的最小割为他们对应节点在最小割树上的路径的边权最小值。
   我们有
   $$\operatorname{mincut}(v _ 1,u _ 2)=d$$
   此外，由于 $d$ 为最小边权，所以
   $$\begin{cases}\operatorname{mincut}(u _ 1,v _ 1)\geq d\\\operatorname{mincut}(u _ 2,v _ 2)\geq d\end{cases}$$
   把上面三式相加，我们可以得到
   $$\operatorname{mincut}(u _ 1,v _ 1)+\operatorname{mincut}(v _ 1,u _ 2)+\operatorname{mincut}(u _ 2,v _ 2)\geq 3d$$
   即对答案的贡献 $\omega$ 满足
   $$\omega\geq 3d$$
2. 顺序为 $u _ 1,u _ 2,v _ 1,v _ 2$，即在连通块之间反复横跳。
   由最小割树的性质：两点间的最小割为他们对应节点在最小割树上的路径的边权最小值。
   我们有
   $$\begin{cases}\operatorname{mincut}(v _ 1,u _ 2)=d\\\operatorname{mincut}(u _ 1,v _ 1)=d\\\operatorname{mincut}(u _ 2,v _ 2)=d\end{cases}$$
   把上面三式相加，我们可以得到
   $$\operatorname{mincut}(u _ 1,v _ 1)+\operatorname{mincut}(v _ 1,u _ 2)+\operatorname{mincut}(u _ 2,v _ 2)=3d$$
   即对答案的贡献 $\omega$ 满足
   $$\omega=3d$$

这就证明了构造方法的正确性。

通过构造方法我们不难发现，每条边的边权只会计算一次，所以我们直接求出最小割树的边权和就是答案了。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=200+5;
const int MAXM=1000+5;

int n,m;

namespace Graph{ //在图上跑网络流
    int cnt=1,head[MAXN],to[MAXM<<1],w[MAXM<<1],Next[MAXM<<1];
    inline void Add_Edge(reg int u,reg int v,reg int len){ //加边
        Next[++cnt]=head[u];
        to[cnt]=v;
        w[cnt]=len;
        head[u]=cnt;
        return;
    }
    inline void Add_Tube(reg int u,reg int v,reg int len){
        Add_Edge(u,v,len);
        Add_Edge(v,u,len); //无向图，所以反向边边权一样
        return;
    }
    int dep[MAXN];
    queue<int> Q;
    inline bool BFS(int s,reg int t){
        memset(dep,-1,sizeof(dep));
        while(!Q.empty())Q.pop();
        dep[s]=1,Q.push(s);
        while(!Q.empty()){
            reg int ID=Q.front();
            Q.pop();
            for(reg int i=head[ID];i;i=Next[i])
                if(dep[to[i]]==-1&&w[i]>0){
                    dep[to[i]]=dep[ID]+1;
                    Q.push(to[i]);
                }
        }
        return dep[t]!=-1;
    }
    int cur[MAXN];
    inline int DFS(reg int ID,reg int t,reg int lim){
        if(ID==t)
            return lim;
        reg int flow=0;
        for(reg int &i=cur[ID];i;i=Next[i])
            if(dep[to[i]]==dep[ID]+1&&w[i]>0){
                reg int f=DFS(to[i],t,min(lim-flow,w[i]));
                if(f){
                    flow+=f;
                    w[i]-=f;
                    w[i^1]+=f;
                }
            }
        return flow;
    }
    inline int Dinic(reg int s,reg int t){
        reg int res=0;
        while(BFS(s,t)){
            memcpy(cur,head,sizeof(head));
            res+=DFS(s,t,INF);
        }
        return res;
    }
    bool vis[MAXN];
    inline void DFS(reg int ID){ //最小割树的标记
        vis[ID]=true;
        for(reg int i=head[ID];i;i=Next[i])
            if(!vis[to[i]]&&w[i]>0)
                DFS(to[i]);
        return;
    }
}

int res[MAXN],tot;

namespace Tree{ //最小割树
    int cnt=1,head[MAXN],to[MAXN<<1],w[MAXN<<1],Next[MAXN<<1];
    inline void Add_Edge(reg int u,reg int v,reg int len){
        Next[++cnt]=head[u];
        to[cnt]=v;
        w[cnt]=len;
        head[u]=cnt;
        return;
    }
    inline void Add_Tube(reg int u,reg int v,reg int len){ //这里要存双向边
        Add_Edge(u,v,len);
        Add_Edge(v,u,len);
        return;
    }
    int d; //d 表示当前发现的最小边权
    int id,x,y; //id 表示边的编号，x,y 表示边的端点
    bool vis[MAXN<<1]; //vis[i] 表示 i 是否被删除
    inline bool DFS(reg int ID,reg int father){
        reg bool flag=false; //判断是否只剩下一个点
        for(reg int i=head[ID];i;i=Next[i])
            if(to[i]!=father&&!vis[i]){
                if(w[i]<d){ //更新
                    id=i;
                    x=ID;
                    y=to[i];
                    d=w[i];
                }
                DFS(to[i],ID);
                flag=true;
            }
        return flag;
    }
    inline void Solve(reg int ID){
        d=INF; //初始化
        if(!DFS(ID,0)){ //只有一个点
            res[++tot]=ID; //直接加入方案中
            return;
        }
        vis[id]=vis[id^1]=true; //删边
        reg int p=x,q=y; //这里要用变量保存，防止递归后变化
        Solve(p),Solve(q);
        return;
    }
}

int W[MAXM<<1];

int main(void){
    n=read(),m=read();
    for(reg int i=1;i<=m;++i){
        static int u,v,w;
        u=read(),v=read(),w=read();
        Graph::Add_Tube(u,v,w);
    }
    static int fa[MAXN];
    for(reg int i=2;i<=n;++i)
        fa[i]=1;
    for(reg int i=1;i<=Graph::cnt;++i)
        W[i]=Graph::w[i];
    reg int ans=0;
    for(reg int i=2;i<=n;++i){
        for(reg int j=1;j<=Graph::cnt;++j)
            Graph::w[j]=W[j];
        reg int s=fa[i],t=i;
        reg int res=Graph::Dinic(s,t);
        ans+=res;
        Tree::Add_Tube(s,t,res);
        memset(Graph::vis,false,sizeof(Graph::vis));
        Graph::DFS(s);
        for(reg int j=i+1;j<=n;++j)
            if(!Graph::vis[j]&&fa[j]==s)
                fa[j]=t;
    }
    printf("%d\n",ans);
    Tree::Solve(1);
    for(reg int i=1;i<=tot;++i)
        printf("%d%c",res[i],i==n?'\n':' '); //输出方案
    return 0;
}