观光之旅
观光之旅
给定一张无向图,求图中一个至少包含3个点的环,环上的节点不重复,并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。
你需要输出最小环的方案,若最小环不唯一,输出任意一个均可。
输入格式
第一行包含两个整数N和M,表示无向图有N个点,M条边。
接下来M行,每行包含三个整数u,v,l,表示点u和点v之间有一条边,边长为l。
输出格式
输出占一行,包含最小环的所有节点(按顺序输出),如果不存在则输出’No solution.’。
数据范围
1≤N≤100,
1≤M≤10000,
1≤l<500
输入样例:
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 // 这个顺序好像不是唯一的应该是只要是这个环内的,随便从某个点开始 , 然后随便按照某个顺序依次下去
#include <iostream>
#include <cstring>
using namespace std;
const int N = 410 ;
const int INF = 0x3f3f3f3f ;
typedef long long ll ;
int a[N][N] , dis[N][N] ; // a 储存 两点之间的距离 dis 储存两点之间的最短路径
int edge[N] ; // edge 存储最小环的路径
int ne[N][N] ; // ne[i][j] 表示从i点到j点这个总的路径上面(很多条边) , i 点的下一个点是什么
int main()
{
int n , m ;
scanf("%d%d" , &n , &m) ;
memset(a , 0x3f , sizeof a) ;
memset(dis , 0x3f , sizeof dis) ;
while(m --)
{
int x , y ,z ;
scanf("%d%d%d", &x , &y , &z) ;
a[x][y] = a[y][x] = dis[x][y] = dis[y][x] = min(dis[x][y] , z) ; // 这个就是怕有重边的,先筛选一下
ne[x][y] = y , ne[y][x] = x ;
// 刚开始以为x和y之间肯定只有一条边,然后x——y路径 x的下一个点就是y ,y的下一个点就是x
}
ll ans = INF ;
int cnt ;
//下面的大体框架就是floyd算法, 三个循环,
for(int k = 1 ;k <= n ;k ++)
{
for(int i = 1 ;i <= n ;i ++)
for(int j = i + 1 ;j <= n ;j ++)
if(ans >0ll + dis[i][j] + a[i][k] + a[k][j]) // 这个地方就是判断最小环的地方,如果存在更小的环就处理一下
{
ans =0ll + dis[i][j] + a[i][k] + a[k][j] ;
cnt = 0 ;
for(int p = i ;p != j ;p = ne[p][j]) // 这个地方就是将i j 两点 组成的很多路径 和最后的一个点k插入edge数组
// p = ne[p][j] ,这个的意思就是p-j路径p的下一个点 ,p从i开始
edge[++ cnt] = p ;
edge[++ cnt] = j , edge[++ cnt] = k ; // 因为 k肯定不在i-j这个最短路径上面,然后单独将其加入
// 因为上面的一个循环到p == j 就停止了,也就是说j这个点并没有被插入,所以也突然插一下
}
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= n ;j ++)
if(dis[i][j] > dis[i][k] + dis[k][j]) // 这个就是floyd主算法
{
dis[i][j] = dis[i][k] + dis[k][j] ;
ne[i][j] = ne[i][k] ; // 额外加了一个这个 ,因为i--j 已经是最短了
// ,此时此刻i-j路径上面只有三个点,因为是从ijk三个点转移过来的 , 所以 i 的下一个点肯定是k
}
}
// 最后就处理一下就行了
if(ans == INF )
cout << "No solution." << endl ;
else
{
for(int i = 1 ;i <= cnt ;i ++)
cout << edge[i] << " " ;
cout << endl ;
}
return 0 ;
}