「LOJ#10072」「一本通 3.2 例 1」Sightseeing Trip（无向图最小环问题）（Floyd

题目描述

原题来自：CEOI 1999

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

输入格式

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

输出格式

输出一个最小环的方案：按环上顺序输出最小环上的点。若最小环不唯一，输出任意一个均可。若无解，输出 No solution.

样例

样例输入

样例输出

1 3 5 2

题解

无向图的最小环问题啊，不知道在多少场考试中间卡住了我的临门一脚。——hzz

教材：http://www.cnblogs.com/Yz81128/archive/2012/08/15/2640940.html#undefined

这个最小环中，一定会有一个编号最大的点。

那么我们设$dp[i][j][k]$为在只经过$1$~$k$的点时，$i$，$j$的最短距离。

那么如果我们设最小环中最大的点为$k$，它两边有点$i$，$j$，

那么答案的最小值就是$dp[i][j][k-1]+g[j][k]+g[k][i]$。

//

然后我们联想Floyd的过程，

$for$ $int$ $k=1$ $to$ $n$

$for$ $int$ $i=1$ $to$ $n$

　　$for$ $int$ $j=1$ $to$ $n$

也就是说，在$k$时，$i$，$j$的最小值都只中转了$1$~$k$的点。

这不就是我们要的$dp[i][j][k]$嘛？！

于是我们可以在Floyd的同时顺便维护答案。

并且$dp$数组的$k$那一维还是可以省掉的。

//详见代码吧qwq

 编号    题目    状态    分数    总时间    内存    代码 / 答案文件    提交者    提交时间

 #    #. 「一本通 3.2 例 」Sightseeing Trip Accepted         ms     KiB    C++ / 1.2 K    qwerta    -- ::

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 #define LL long long

 int g[][];//直接连边的距离

 int dis[][];//有中转点的距离

 int q[];

 int toq=;

 int zz[][];//zz[i][j]表示从i到j的最小路径的中转点

 void getpath(int u,int v)

 {

     if(!zz[u][v])return;

     getpath(u,zz[u][v]);//从u往中转点找

     q[++toq]=zz[u][v];

     getpath(zz[u][v],v);

     return;

 }

 int main()

 {

     //freopen("a.in","r",stdin);

     int n,m;

     scanf("%d%d",&n,&m);

     memset(g,,sizeof(g));

     for(int i=;i<=n;++i)

       g[i][i]=;

     for(int i=;i<=m;++i)

     {

         int x,y,l;

         scanf("%d%d%d",&x,&y,&l);

         g[x][y]=min(g[x][y],l);

         g[y][x]=g[x][y];

     }

     memcpy(dis,g,sizeof(g));

     long long ans=1e9+;

     for(int k=;k<=n;++k)

     {

         for(int i=;i<k;++i)

         for(int j=i+;j<k;++j)//因为k为环内最大点，所以只能循环到k-1

         {

             if(1LL*dis[i][j]+g[j][k]+g[k][i]<ans)

             {

                 ans=dis[i][j]+g[j][k]+g[k][i];

                 toq=;

                 q[++toq]=i;

                 getpath(i,j);

                 q[++toq]=j;

                 q[++toq]=k;

             }

         }

         //然后是正常Floyd

         for(int i=;i<=n;++i)

         for(int j=;j<=n;++j)

         {

             if(1LL*dis[i][k]+dis[k][j]<dis[i][j])

             {

                 dis[i][j]=dis[i][k]+dis[k][j];

                 zz[i][j]=k;

             }

         }

     }

     if(!toq){cout<<"No solution.";return ;}

     for(int i=;i<=toq;++i)

       cout<<q[i]<<" ";

     return ;

 }

巴特西