POJ1734-Sightseeing trip(Floyd+最小环)

题目链接:POJ1734-Sightseeing trip

题意:

给一个无向图带权图,求其中的最小简单环(点数>=3)。

题解:

Floyd变形。

考虑一个环上的所有点,一定有一个编号最大的点;

用Floyd求最小环:u->···->v->k->u,其中k是与u,v均相邻的点。若保证v->u这段不经过k,那么就形成了一个环;

只要k>u,k>v即可保证不经过k。

参考代码:

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e2+9;
const int inf=99999999;
int n,m,cnt;
int mp[MAXN][MAXN],dis[MAXN][MAXN];
int pre[MAXN][MAXN],path[MAXN];
int Floyd()
{
    int minV=inf;
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<k; i++)
            for(int j=i+1; j<k; j++)
                if(minV>dis[i][j]+mp[j][k]+mp[k][i])
                {
                    minV=dis[i][j]+mp[j][k]+mp[k][i];
                    int p=j;
                    cnt=0;
                    while(p!=i)
                    {
                        path[++cnt]=p;
                        p=pre[i][p];//pre[i][j]记录i->j路线上j的前一个点
                    }
                    path[++cnt]=i;
                    path[++cnt]=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];
                    pre[i][j]=pre[k][j];
                }
    }
    return minV;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            dis[i][j]=mp[i][j]=inf;
            pre[i][j]=i;
        }
    for(int i=1; i<=m; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        mp[u][v]=min(mp[u][v],w);
        dis[u][v]=dis[v][u]=mp[v][u]=mp[u][v];
    }
    int ans=Floyd();
    if(ans!=inf)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                printf("%d ",pre[i][j]);
            puts("");
        }
        for(int i=1;i<=cnt;i++)
            printf("%d ",path[i]);
    }
    else
        puts("No solution.");
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。