自动搬运

查看原文

来自洛谷，原作者为

	ivyjiao 复活了

搬运于2025-08-24 23:02:35，当前版本为作者最后更新于2024-09-17 15:31:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷什么时候把这题 SPJ 修一修啊……

LOJ AC 记录。

相信大家都做过 P6175 无向图的最小环问题。而那题是本题的严格弱化版。

什么？没做过？

我们简单回顾下，在那题的最高赞题解中提到：

在 Floyd 算法枚举 $k$ 的时候，已经得到了前 $k-1$ 个点中每两个点的最短路径，这 $k-1$ 个点不包括点 $k$，并且他们的最短路径中也不包括 $k$ 点。

那么我们便可以从这前 $k-1$ 个点中选出两个点 $(i,j)$ 来，因为 $dis_{i,j}$ 已经是此时 $(i,j)$ 间的最短路径，且这个路径不包含 $k$ 点。

所以连接 $i\to j\to k\to i$ ，我们就得到了一个经过 $(i,j,k)$ 的最小环。

容易发现，本题只需要稍微推导可以转化为以上形式。唯一不同只在输出方案。

那么既然本题的难度升了两个颜色，输出方案想必很难吧！（其实按作者愚见，P6175 应该升绿……）

其实不难，只需要在每次更新最短路时把方案更新就行，记录方案的操作是很常规的，由于数据范围很小，所以不用担心超时。

首先 $j\to k\to i$ 这部分是没变的，只需要把 $i\to j$ 的部分更新掉就行了。具体的方法，就是记录 $p$ 数组，$p_{i,j}=k$ 代表上次 $p_{i,j}$ 是从 $dis_{i,k}+dis_{k,j}$ 转移来的，每次递归跳 $(i,p_{i,j})$ 和 $(p_{i,j},j)$ 即可，而如果 $p_{i,j}=0$，说明 $g_{i,j}$ 即为 $(i,j)$ 最短路径，直接返回。

局部代码如下：

void check(int x,int y){
	if(!p[x][y]) return;
	check(x,p[x][y]);
	path.push_back(p[x][y]);
	check(p[x][y],y);
}
......
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if((long long)dis[i][j]+g[i][k]+g[k][j]<ans){
                    ans=dis[i][j]+g[i][k]+g[k][j];
                    path.clear();
					path.push_back(i);
					check(i,j);
					path.push_back(j);
					path.push_back(k);
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                    p[i][j]=k;
                }
            }
        }

完整代码如下：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,m,u,v,d,dis[101][101],g[101][101],p[101][101],ans=0x3f3f3f3f;
vector<int>path;
void check(int x,int y){
	if(!p[x][y]) return;
	check(x,p[x][y]);
	path.push_back(p[x][y]);
	check(p[x][y],y);
}
int main(){
    cin>>n>>m;
    memset(dis,0x3f,sizeof dis);
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++){
        dis[i][i]=0;
        g[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        cin>>u>>v>>d;
        dis[u][v]=min(dis[u][v],d);
        dis[v][u]=min(dis[v][u],d);
        g[u][v]=min(g[u][v],d);
        g[v][u]=min(g[v][u],d);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if((long long)dis[i][j]+g[i][k]+g[k][j]<ans){
                    ans=dis[i][j]+g[i][k]+g[k][j];
                    path.clear();
					path.push_back(i);
					check(i,j);
					path.push_back(j);
					path.push_back(k);
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                    p[i][j]=k;
                }
            }
        }
    }
    if(ans==0x3f3f3f3f) cout<<"No solution.";
    else for(int i=0;i<path.size();i++) cout<<path[i]<<" ";
}