POJ 1734 Sightseeing trip

題目大意：

在一張無向圖上求一個不是自環的最小環

分析：

好難呀，如果隻求最小環的權值我還勉強可以寫出來，但是加上記錄路徑就完全不會了，覺得自己弱爆了Ｏ(≧口≦)Ｏ

先說怎麼求最小環：

我們考慮這樣一個問題，怎麼求最短路？很簡單Floyd、dijkstra,etc.，那麼最小環呢？是以我們就要先考慮環和路徑之間有什麼關系，很明顯，環是由路徑連接配接而成的，詳細來說，一個i~i的環可以拆成三條邊i~k的直接路徑，k~j的直接路徑以及i~j的最短路徑。為什麼要這麼拆呢？為什麼不拆成兩條最短路徑或者三條最短路徑呢？這就是Floyd的功勞了，我們考慮Floyd是怎麼求最短路的，dis[i][j]=min(dis[i][k]+dis[k][j]),我們是通過枚舉ij之間的中間點k來更新ij之間的最短路徑，是以我們也可以通過枚舉點k來更新ii之間的最短路徑，也就是環，但是直接更新肯定不行，因為我們無法保證我們求出的ij之間的最短路不包含k，是以怎麼辦呢？我們可以強制要求k是環上編号最大的點，然後通過枚舉k來更新最小環。

接下來就是很難想到的路徑記錄問題了：我們可以發現，一條從i到j的路徑，如果看成有向邊的話，每個點都有在這條路徑上的唯一father節點，有了這個想法，這個問題就很好解決了，我們記錄一下ij之間的最短路徑上每個節點的pre值，在更新dis的時候，更新pre

代碼如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x7ffffff//注意inf不能開太小會WA太大會RE
using namespace std;
const int maxn=+;
int mp[maxn][maxn],n,m,path[maxn],cnt,pre[maxn][maxn],dis[maxn][maxn],ans;
inline int read(){
    char ch=getchar();
    int f=,x=;
    while(!(ch>='0'&&ch<='9')){
        if(ch=='-')
            f=-;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        x=x*+ch-'0',ch=getchar();
    return f*x;
}
signed main(void){
    while(scanf("%d%d",&n,&m)!=EOF){
        cnt=,ans=inf;
        for(int i=;i<=n;i++)
            for(int j=;j<=n;j++)
                pre[i][j]=i,mp[i][j]=dis[i][j]=inf;
        for(int i=,x,y,z;i<=m;i++)
            x=read(),y=read(),z=read(),dis[x][y]=dis[y][x]=mp[x][y]=mp[y][x]=min(mp[x][y],z);
        for(int k=;k<=n;k++){
            for(int i=;i<k;i++)
                for(int j=i+;j<k;j++)
                    if(ans>mp[i][k]+mp[k][j]+dis[i][j]){
                        ans=mp[i][k]+mp[k][j]+dis[i][j];//dis--最短距離，mp---直接距離 
                        cnt=;
                        int tmp=j;
                        while(tmp!=i){
                            path[++cnt]=tmp;
                            tmp=pre[i][tmp];                        
                        }
                        path[++cnt]=i,path[++cnt]=k;
                    }
            for(int i=;i<=n;i++)
                for(int j=;j<=n;j++)
                    if(dis[i][j]>dis[i][k]+dis[k][j]){
                        dis[i][j]=dis[i][k]+dis[k][j];
                        pre[i][j]=pre[k][j];
                    }
        }
        if(ans==inf)
            printf("No solution.\n");
        else{
            for(int i=;i<=cnt;i++)
                cout<<path[i]<<" ";
            cout<<endl;
        }
    }
    return ;
}
           

by >o< neighthorn