Sightseeing trip

POJ

题意:给定n个点m条边的无向图,求最小环并输出方案.最小环:至少包含3个节点,环上的节点不重复且长度之和最小.\(n<=100\)

看到这个数据范围就容易想到\(floyd\),设\(dis[i][j]\)存图,设\(dist[i][j]\)表示经过编号不超过k-1的节点 从i到j的最短路长度.则\(ans=min_{dist[i][j]+dis[j][k]+dis[k][i]}.\)(其中\(1<=i<j<k\)这样才能保证节点编号不超过k-1).我们在每次更新dist数组之前先跑一遍这个来更新答案.

至于输出路径方案,就在每次能够更新ans的时候更新就好了.另外开一个数组\(pos[i][j]\)记录更新\(dist[i][j]\)时的中转点k.这样就能够根据i,j不断递归下去找到路径i,j间的所有点了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=105;
vector<int>path;
int dis[N][N],dist[N][N],pos[N][N];
inline void get_path(int x,int y){
    if(!pos[x][y])return;
    get_path(x,pos[x][y]);
    path.push_back(pos[x][y]);
    get_path(pos[x][y],y);
}
int main(){
    memset(dis,0x3f,sizeof(dis));
    int n=read(),m=read(),ans=1e9;
    for(int i=1;i<=m;++i){
        int a=read(),b=read(),c=read();
        dis[a][b]=dis[b][a]=min(dis[a][b],c);
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            dist[i][j]=dis[i][j];
    for(int k=1;k<=n;++k){
        for(int i=1;i<k;++i)
            for(int j=i+1;j<k;++j)
                if((ll)dist[i][j]+dis[j][k]+dis[k][i]<ans){//不开long long见zz
                    ans=dist[i][j]+dis[j][k]+dis[k][i];
                    path.clear();
                    path.push_back(i);
                    get_path(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(dist[i][j]>dist[i][k]+dist[k][j]){
                    dist[i][j]=dist[i][k]+dist[k][j];
                    pos[i][j]=k;
                }
    }
    if(ans==1e9){
        puts("No solution.");
        return 0;
    }
    for(int i=0;i<path.size();++i)printf("%d ",path[i]);
    puts("");
    return 0;
}

Sightseeing trip

原文：https://www.cnblogs.com/PPXppx/p/11559336.html