「LOJ#10072」「一本通 3.2 例 1」Sightseeing Trip（无向图最小环问题）（Floyd

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目描述

原题来自：CEOI 1999

给定一张无向图，求图中一个至少包含 333 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。若无解，输出 No solution.。图的节点数不超过 100100100。

输入格式

第一行两个正整数 n,mn,mn,m 表示点数和边数。
接下来 mmm 行，每行三个正整数 x,y,zx,y,zx,y,z，表示节点 x,yx,yx,y 之间有一条长度为 zzz 的边。

输出格式

输出一个最小环的方案：按环上顺序输出最小环上的点。若最小环不唯一，输出任意一个均可。若无解，输出 No solution.

样例

样例输入

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

样例输出

1 3 5 2

题解

无向图的最小环问题啊，不知道在多少场考试中间卡住了我的临门一脚。——hzz

教材：http://www.cnblogs.com/Yz81128/archive/2012/08/15/2640940.html#undefined

这个最小环中，一定会有一个编号最大的点。
那么我们设$dp[i][j][k]$为在只经过$1$~$k$的点时，$i$，$j$的最短距离。
那么如果我们设最小环中最大的点为$k$，它两边有点$i$，$j$，
那么答案的最小值就是$dp[i][j][k-1]+g[j][k]+g[k][i]$。
//
然后我们联想Floyd的过程，
$for$ $int$ $k=1$ $to$ $n$
$for$ $int$ $i=1$ $to$ $n$
$for$ $int$ $j=1$ $to$ $n$
也就是说，在$k$时，$i$，$j$的最小值都只中转了$1$~$k$的点。
这不就是我们要的$dp[i][j][k]$嘛？！
于是我们可以在Floyd的同时顺便维护答案。
并且$dp$数组的$k$那一维还是可以省掉的。
//详见代码吧qwq

编号题目状态分数总时间内存代码 / 答案文件提交者提交时间
# #. 「一本通 3.2 例」Sightseeing Trip Accepted ms KiB C++ / 1.2 K qwerta -- :: #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
int g[][];//直接连边的距离
int dis[][];//有中转点的距离
int q[];
int toq=;
int zz[][];//zz[i][j]表示从i到j的最小路径的中转点
void getpath(int u,int v)
{
if(!zz[u][v])return;
getpath(u,zz[u][v]);//从u往中转点找
q[++toq]=zz[u][v];
getpath(zz[u][v],v);
return;
}
int main()
{
//freopen("a.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
memset(g,,sizeof(g));
for(int i=;i<=n;++i)
g[i][i]=;
for(int i=;i<=m;++i)
{
int x,y,l;
scanf("%d%d%d",&x,&y,&l);
g[x][y]=min(g[x][y],l);
g[y][x]=g[x][y];
}
memcpy(dis,g,sizeof(g));
long long ans=1e9+;
for(int k=;k<=n;++k)
{
for(int i=;i<k;++i)
for(int j=i+;j<k;++j)//因为k为环内最大点，所以只能循环到k-1
{
if(1LL*dis[i][j]+g[j][k]+g[k][i]<ans)
{
ans=dis[i][j]+g[j][k]+g[k][i];
toq=;
q[++toq]=i;
getpath(i,j);
q[++toq]=j;
q[++toq]=k;
}
}
//然后是正常Floyd
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
{
if(1LL*dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
zz[i][j]=k;
}
}
}
if(!toq){cout<<"No solution.";return ;}
for(int i=;i<=toq;++i)
cout<<q[i]<<" ";
return ;
}