题解：P5776 [SNOI2013] Quare

· · 题解

题意

给你一张有重边、无自环的无向正权图，求出它边权和最小的边双连通生成子图的边权和。

思路简述

感觉截至 2025/4/24 的题解对状压部分的讲解不够详细，所以专门开一篇题解讲状压部分。

关于耳分解的定义，网络上能搜集到多种版本，下文中使用“将一张图不断删去耳(包括所有边和除两端外的所有点)，使得最后仅剩环 G_0”这一版本进行转移。

考虑思考其逆过程，分为两部分，找到 G_0，然后添加耳。

令 f_{msk} 为原图点集为 msk 导出子图的边权和最小的边双连通生成子图的边权和；e_{i,j} 为连接 i,j 两点的最小边；dp_{msk,i,j} 为考虑 msk 中的点，当前存在一个未构建完成的耳（即一条链，链的一端在已经边双连通的部分上），除链外所有点边双连通，链不在边双连通部分上的端点为 i，且最终链会接到 j 上的最小边权和。

我们会有以下几种转移（注意转移顺序，1 必须在 2,3 前）：

对于一开始找 G_0 环的部分，我们也可以使用相似的转移，甚至将两部分共用一个数组进行。

但我们发现上述转移过程实际上是存在问题的，对于一个二元环，两点间的最小边会被重复经过。解决方案是预处理两点间的最小边和次小边，特判二元环。此外，在转移 1 中，我们需保证不会构建出二元环。我的处理方案是给 dp 数组增设 0/1 维，表示当前的链能否停止扩张，与 j 相接。题解区中还给出了其他处理手段，然而本人看不懂。

至此本题解决完毕。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,e[12][12][2],f[(1<<12)+5],dp[(1<<12)+5][12][12][2];
inline bool isin(int msk,int p){return (msk>>p)&1;}
inline void solve(){
    memset(e,0x1f,sizeof(e));
    memset(f,0x1f,sizeof(f));
    memset(dp,0x1f,sizeof(dp));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        u--,v--;
        if(e[u][v][0]>w) e[u][v][1]=e[u][v][0],e[u][v][0]=w;
        else if(e[u][v][1]>w) e[u][v][1]=w;
        swap(u,v);
        if(e[u][v][0]>w) e[u][v][1]=e[u][v][0],e[u][v][0]=w;
        else if(e[u][v][1]>w) e[u][v][1]=w;
    }
    //找G0环部分
    for(int s=0;s<n;s++)
        for(int t=0;t<n;t++)//特判二元环
            if(s!=t) f[(1<<s)|(1<<t)]=min(f[(1<<s)|(1<<t)],e[s][t][0]+e[s][t][1]);
    for(int s=0;s<n;s++)//枚举G0环的起点(起点即终点)
        for(int k=0;k<n;k++)//走一步
            dp[(1<<s)|(1<<k)][k][s][1]=e[s][k][0];
    //加耳部分
    for(int msk=1;msk<(1<<n);msk++){
        //特判二元环
        for(int s=0;s<n;s++)
            for(int t=0;t<n;t++)
                if(isin(msk,s)&&!isin(msk,t))
                    f[msk|(1<<t)]=min(f[msk|(1<<t)],f[msk]+e[s][t][0]+e[s][t][1]);
        //完成当前的耳/G0环
        for(int s=0;s<n;s++)
            for(int t=0;t<n;t++)
                f[msk]=min(f[msk],dp[msk][s][t][0]+e[s][t][0]);//通过 0/1 维无视二元环
        //枚举耳的起点和终点,新开一个耳
        for(int s=0;s<n;s++)
            for(int t=0;t<n;t++)
                if(isin(msk,s)&&isin(msk,t))
                    dp[msk][s][t][s==t]=min(dp[msk][s][t][s==t],f[msk]);//起点终点相等要注意排除二元环
        //在扩张当前的链/G0环
        for(int s=0;s<n;s++)
            for(int t=0;t<n;t++)
                for(int k=0;k<n;k++)//我们要从 s 走到 k
                    for(int op:{0,1})
                        if(isin(msk,s)&&isin(msk,t)&&!isin(msk,k)){
                            int nop=op&(s==t);
                            dp[msk|(1<<k)][k][t][nop]=min(dp[msk|(1<<k)][k][t][nop],dp[msk][s][t][op]+e[s][k][0]);
                        }
    }
    if(f[(1<<n)-1]<1e9) cout<<f[(1<<n)-1]<<'\n';
    else cout<<"impossible\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}