问题描述

大意就是给你一个无向图,求出它的最小环。
并输出最小环上的点。(会有SPJ)

输出

第一行n(n<=100), m(m<=10000)。表示有n个点,m条边。
接下来m行,每一行描述一条边。

输出

输出最小环上的所有节点

思路

求最小环是用Floyd的方法。

我们按顺序枚举所有点,再枚举与该点相邻的点对。枚举点对时,我们可以不需要考虑编号比该点大的点,因为编号比它大的点在后面会被枚举到,会包含这种情况。环的长度就是该点到点对的距离与点对之间的距离之和。

接下来考虑输出环上的点。记录路径感觉很难,于是膜了一下书上的做法。每进行一次松弛操作时就记录一下。环上的点就是点对之间的最短路径上的点和该点对。可以递归下去找最短路径上的点,有点像记录DP方案。(似乎有点难讲清楚,代码还是比较好懂的)。

细节

  1. 小心有重边。
  2. 枚举完点对之后不要忘记Floyd更新点之间的距离
  3. 更新ans时一点要开longlong (代码38行)
  4. 记录路径时递归不要弄错了
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define MAXN 105
#define INF 0x3f3f3f3f
using namespace std;

int n, m, x, y, z, ans=INF, mmp[MAXN][MAXN], dis[MAXN][MAXN], f[MAXN][MAXN];
vector<int> path;

void find(int i, int j)
{
    if(!f[i][j]) return;
    find(i, f[i][j]);
    path.push_back(f[i][j]);
    find(f[i][j], j);
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(mmp, 0x3f, sizeof(mmp));
    memset(dis, 0x3f, sizeof(dis));
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        if(mmp[x][y]<z) continue;
        mmp[x][y]=mmp[y][x]=z;
        dis[x][y]=dis[y][x]=z;
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<k; i++)
            for(int j=i+1; j<k; j++)
            {
                if(ans>(long long)dis[i][j]+mmp[i][k]+mmp[k][j])
                {
                    path.clear();
                    path.push_back(i);
                    find(i, j);
                    path.push_back(j);
                    path.push_back(k);
                    ans=dis[i][j]+mmp[i][k]+mmp[k][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])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                    f[i][j]=k;
                }
            }
    }
    if(ans==INF) printf("No solution.");
    else for(int i=0; i<path.size(); i++) printf("%d ", path[i]);
} 

2 对 “POJ1734 Sightseeing trip [Floyd]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注