P6175 无向图的最小环问题

提交入口：https://www.luogu.com.cn/problem/P6175

网上没找到满意的题解，大佬们微言大义，不是很能看懂。我在这里留下分析的大致思路，不保证正确，欢迎讨论。

题目描述

给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。

输入格式

第一行两个正整数 $n,m$ 表示点数和边数。

接下来 $m$ 行，每行三个正整数 $u,v,d$，表示节点 $u,v$ 之间有一条长度为 $d$ 的边。

输出格式

输出边权和最小的环的边权和。若无解，输出 No solution.。

样例 #1

样例输入 #1

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

样例输出 #1

61

提示

样例解释：一种可行的方案：$1-3-5-2-1$。

对于 $20\%$ 的数据，$n,m \leq 10$。

对于 $60\%$ 的数据，$m\leq 100$。

对于 $100\%$ 的数据，$1\le n\leq 100$，$1\le m\leq 5\times 10^3$，$1 \leq d \leq 10^5$。

无解输出包括句号。

---

分析 & 代码

错误思路

本题不存在优于$O(n^3)$很多的算法，请停止无谓的尝试。

不过在尝试的过程中我也理解了一些东西…改动的tarjan部分也许可以记一下，所以还是决定贴出来备忘。

#include<cstdio>
#include<cstring>
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int maxn = 103;
const int maxm = 5003;
const int INF = 0x7fffffff;
int head[maxn],tot,depth[maxn],fa[maxn],fa2[maxn],dis[maxn][maxn];
int low[maxn],dfn[maxn],stac[maxn],num,ans,n,m,top,uset[maxn];
struct Edge{int v,w,next;}edge[maxm<<1];
bool vis[maxn],ins[maxn];

void makeset(int size){
    for(int i=0;i<size;i++)uset[i]=i;
}

int find(int x){
    if(x!=uset[x])uset[x]=find(uset[x]);
    return uset[x];
}

void unionset(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    uset[x]=y;
}

inline void addedge(int x,int y,int z){
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

void tarjan(int x){
    low[x]=dfn[x]=++num;
    stac[++top]=x; ins[x]=true;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(!dfn[y]){
            fa2[y]=x;
            tarjan(y);
            low[x]=MIN(low[x],low[y]);
        }
        else if(ins[y]&&y!=fa2[x]){
            low[x]=MIN(low[x],dfn[y]);
        }
    }
    if(dfn[x]==low[x]){
        int y;
        do{
            y=stac[top--];
            ins[y]=false;
            unionset(x,y);
        }while(x!=y);
    }
}

void dfs(int x,int dep){ //可能有重边
    vis[x]=true;
    depth[x]=dep;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(!vis[y]){
            fa[y]=x;
            dfs(y,depth[x]+dis[x][y]);
        }
        else if(y!=fa[x]&&(depth[x]-depth[y]>0)&&(find(x)==find(y))){
            ans=MIN(ans,dis[x][y]+depth[x]-depth[y]);
        }
    }
    return;
}

int main(){
    scanf("%d%d",&n,&m);
    ans=INF;
    makeset(n+1);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x==y)continue;
        if(z<dis[x][y]||(!dis[x][y])){
            addedge(x,y,z);
            addedge(y,x,z);
            dis[x][y]=dis[y][x]=z;
        }
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i);

    for(int s=1;s<=n;s++){
        memset(fa,0,sizeof(fa));
        memset(vis,false,sizeof(vis));
        memset(depth,0,sizeof(depth));
        dfs(s,0); int i=s+1;
        while(i<=n){
            if(!vis[i])dfs(i,0);
            i++;
        }
        int j=1;
        while(j<s){
            if(!vis[j])dfs(j,0);
            j++;
        }
    }

    if(ans==INF)printf("No solution.");
    else printf("%d",ans);
    return 0;
}

以下数据将得不到正确答案：

5 10
4 2 3
5 2 5
3 4 2
5 3 4
2 3 3
1 5 5
2 1 1
5 4 2
1 4 2
1 3 4

原因在于，上面那个算法假了，想要穷尽所有情况，复杂度还得上一维，且常数巨大。

正确思路

定义： 设 $R_{i,j,k}$ 为经过编号为$i$，$j$，$k$ 节点的最小环。

$R_{i,j,k}$ 可以不存在。

考虑集合 $Ring=\{ R_{i,j,k}|1\leqslant i<j<k \leqslant n \}$ ，我们指出，符合题目要求的最小环 $r\in Ring$ 。

证明： $r$ 的节点数大于等于3，任取其中3个$a$，$b$，$c$ ，不妨设$a<b<c$。因为 $r$ 是全图中最小的环，所以 $r$ 也是经过 $a$，$b$，$c$ 的最小环。则 $r=R_{a,b,c}\in Ring$ ，证毕。

于是在算法上，只需要枚举集合 $Ring$ ，并不断更新ans。这提示我们从$floyd$考虑。简述$floyd$算法如下：

设$D_{i,j,k}$为 $i$ 到 $j$ 的只以 $(1…k)$ 集合中的节点为中间节点的最短路长度。
若最短路经过点 $k$，则$D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}$
若最短路不经过点 $k$，则$D_{i,j,k}=D_{i,j,k-1}$
因此，$D_{i,j,k}=\mathrm{min}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})$

先给出代码：

#include <cstdio>
#define MIN(a,b) ((a)<(b)?(a):(b))
using LL = long long;
using namespace std;

const LL INF = 1e13+3;
LL n,m,ans=INF;
LL dis[103][103],mcopy[103][103];

int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)dis[i][j]=mcopy[i][j]=INF;
    
    for(int i=1;i<=m;i++){
        LL x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        dis[x][y]=dis[y][x]=MIN(dis[x][y],z);
        mcopy[x][y]=mcopy[y][x]=dis[x][y];
    }

    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++) //k=2时也不会执行
                ans=MIN(ans,dis[i][j]+mcopy[j][k]+mcopy[k][i]);      
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=dis[j][i]=MIN(dis[i][j],dis[i][k]+dis[k][j]);
    }

    if(ans==INF)printf("No solution.");
    else printf("%lld",ans);
    
    return 0;
}

这看起来有点奇怪。记住我们的目标是枚举集合$Ring$，这里解释以下核心代码：

//for循环首次不满足条件便退出
//奇怪的现象，不知道自己为什么会为此产生疑问
for(int k=1;k<=n;k++){
    for(int i=1;i<k;i++)
        for(int j=i+1;j<k;j++) //k=2时也不会执行
            ans=MIN(ans,dis[i][j]+mcopy[j][k]+mcopy[k][i]);      
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=dis[j][i]=MIN(dis[i][j],dis[i][k]+dis[k][j]);
}

首先，由枚举顺序，已经有 $1\leqslant i<j<k \leqslant n$ 。

在Floyd枚举k的时候，已经得到了 $i,j (1\leqslant i\ne j \leqslant n)$ 只以 $\{ 1,…,k-1\}$ 集合中的节点为中间节点的最短路长度 $D_{i,j,k-1}$，它在代码中就是dis[i][j]。

为什么第6行dis[i][j]加的是mcopy[][]？

从生成的角度去理解它：k要在环中，必然要从k中伸出边，设伸出的两个边连的点是 i 和 j 。那么 $D_{i,j,k-1}$ 加上两个边的长度就是环的长度。而这两个边是原始数据输入的长度。

一个可能的疑惑：$D_{i,j,k-1}$ 不是 $D_{i,j,n}$ ，为什么要这样，直觉上用$D_{i,j,n}$ 不是更好吗？

答案是不能且不必要：

• 若 $D_{i,j}$ 经过 k 点，不成环，使用$D_{i,j,n}$ 会得到错误答案。因此不能。
• 若 $D_{i,j}$ 不经过 k 及编号以后的点，$D_{i,j,n}=D_{i,j,k-1}$，
• 若 $D_{i,j}$ 经过 k 以后的点，考虑下图： 这里需要反过来考虑：设 $p$ 为 $D_{i,j}$ 经过的最大的节点编号，则就长度而言 $R_{i,j,k}\geqslant R_{i’,j’,p}$ （这里$R_{i’,j’,p}$的存在性已经保证），因为 $D_{i’,j’}\leqslant \mathrm{len}\{i’,i,k,j,j’ \}$ 。而在后面的计算中，$R_{i’,j’,p}$ 会被计算到，如果合适，它会作为更优解更新ans。

顺带一提，集合 $Ring$ 中所有元素都会被枚举到。

$$\mathcal{THE}\quad \mathcal{END}$$