Sightseeing Trip

问题描述

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

输入格式

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

输出格式

输出一个最小环的方案：按环上顺序输出最小环上的点。若最小环不唯一，输出任意一个均可。若无解，输出 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

思路

对于每一对联通的点\(i,j\)考虑是否存在一个环经过未遍历到的点\(k\)，环的长度为:

\[d=dis[i][j]+edge[j][k]+edge[k][i] \\ans=min(ans,d) \]

考虑所有的\(k\)最后取构成环的最小值，在这过程中不断用floyd算法更新最短路径长度，并且记录路径。

Code

/**********************************************************
* @Author: 			   Kirito
* @Last Modified by:   Kirito
* @Remark:
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;

const int maxn=411;
//graph
int n,m,mp[maxn][maxn],dis[maxn][maxn],pos[maxn][maxn];
//ans
vector<int> path;

void getPath(int x,int y){
    if(pos[x][y]==0) return;
    getPath(x,pos[x][y]);
    path.push_back(pos[x][y]);
    getPath(pos[x][y],y);
    return;
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	#endif
    FAST;
    cin>>n>>m;
    CSE(mp,INF);CSE(dis,INF);CSE(pos,0);
    for(int i=1;i<=n;i++) mp[i][i]=dis[i][i]=0;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        mp[y][x]=mp[x][y]=dis[x][y]=dis[y][x]=z;
    }
    ll  ans=INF;
    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if(ans>ll(dis[i][j]+mp[j][k]+mp[k][i])){
                    ans=dis[i][j]+mp[j][k]+mp[k][i];
                    path.clear();
                    path.push_back(i);
                    getPath(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][j]>dis[i][k]+dis[k][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                    pos[i][j]=k;
                }
            }
        }
    }
    if(ans>=INF)
        cout<<"No solution."<<endl;
    else{
        for(int i=0;i<int(path.size());i++)
            cout<<path[i]<<" ";
        cout<<endl;
    }
	return 0;
}