题目：无向图的最小环问题
原题传送门
https://www.luogu.com.cn/problem/P6175
题目描述
给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。
输入格式
第一行两个正整数 $n,m$ 表示点数和边数。
接下来 $m$行，每行三个正整数 $u,v,d$，表示节点 $u,v$ 之间有一条长度为 $d$ 的边。
数据不保证无重边、自环。
输出格式
输出边权和最小的环的边权和。若无解，输出 No solution.。
输入输出样例
输入
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20输出
61题解
这就是一道算法很裸露的题，没有什么阅读理解。
分析
这是一个无向图，可以用floyd算法帮助我们进行求解计算。
首先先分析一下floyd算法。
可以计算任意两点间的最短路。是一个三层循环的算法,时间复杂度$O(n^3)$。$dist[ i][ j ]$ 表示$i $到 $j$ 的最短距离。
for(int k = 1; k <= n; k ++ )
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
dist[i][j] = min(dist[i][k] + dist[k][j] , dist[i][j]);先分析一下，状态转移过程和 $k$ 的含义 ，假设i 走向j 的前一个点是 k，计算由 i 走到 j 的 最短路 。我们可以看出，当外层循环$k$刚开始时，$dist[i][j]$保存着 经过编号不超过 $k-1$节点 从 $i$到 $j$的最短路长度。
如何构造出一个环呢？
图的左边我们经过了 k-1个点由$j$ 点 到 $i$，图的右边经过第 k 个点由 $i$到$j$，这样我们就构成了环。
左边和右边点会重复吗？
你看枚举 $k$的过程，不会重复的。因为bulabula
于是最小环的状态计算我们就可以表示出来了。
$min_{1\leq i <j <k }(dist[i][j] + a[i][k] + a[k][j])$
a[i][k]表示 由i 到k 那条边的距离。
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 110;
int g[N][N]; //图
int dist[N][N]; //floyd的
int n , m ;
int main(){
cin>>n>>m;
memset( g , 0x3f , sizeof g );
for( int i = 1 ; i <= n ; i ++ ) g[i][i] = 1 ;
while ( m -- )
{
int a , b , c ;
cin>>a>>b>>c;
g[a][b] = g[b][a] = min( g[a][b] , c ); //有重环
}
//floyd
int ans = 0x3f3f3f3f; //记录最先环大小
memcpy( dist , g , sizeof dist );
for( int k = 1 ; k <= n ; k ++ ) //floyd 一层
{
for( int i = 1 ; i < k ; i ++ ){
for( int j = i + 1 ; j < k ; j ++ ){
if( ans > (long long )dist[i][j] + g[i][k] + g[k][j] ){
ans = dist[i][j] + g[i][k] + g[k][j];
}
}
}
for( int i = 1 ; i <= n ; i ++ ) //floyd 二层
for( int j = 1 ; j <= n ; j ++ ) //floyd 三层
dist[i][j] = min(dist[i][k] + dist[k][j] , dist[i][j]);
}
if( ans == 0x3f3f3f3f ) cout<<"No solution.";
else cout<<ans;
system("pause");
return 0;
}poj1734 Sightseeing trip 是带阅读理解的求最小环，并输出最小环所经过的点， 代码如下。
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 110;
int g[N][N]; //图
int dist[N][N]; //floyd的
int path[N][N]; //记录路径由哪个点转移过来的
int n , m ;
int cnt , p[N];
void get_path( int i , int j ){
if( path[i][j] == 0 ) return ;
int k = path[i][j];
get_path( i , k );
p[ cnt ++ ] = k;
get_path( k , j );
}
int main(){
cin>>n>>m;
memset( g , 0x3f , sizeof g );
for( int i = 1 ; i <= n ; i ++ ) g[i][i] = 1 ;
while ( m -- )
{
int a , b , c ;
cin>>a>>b>>c;
g[a][b] = g[b][a] = min( g[a][b] , c );
}
//floyd
int ans = 0x3f3f3f3f;
memcpy( dist , g , sizeof dist );
for( int k = 1 ; k <= n ; k ++ )
{
for( int i = 1 ; i < k ; i ++ ){
for( int j = i + 1 ; j < k ; j ++ ){
if( ans > dist[i][j] + g[i][k] + g[k][j] ){
ans = dist[i][j] + g[i][k] + g[k][j];
cnt = 0 ;
p[cnt ++ ] = k;
p[cnt ++ ] = i;
get_path(i , j );
p[cnt ++ ] = j;
}
}
}
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];
path[i][j] = k ;
}
}
}
}
if( ans == 0x3f3f3f3f ) cout<<"No solution";
else for( int i = 0 ; i < cnt ; i ++ ) cout<<p[i]<<" ";
system("pause");
return 0;
}对于有向图的最小环问题，可枚举起点S=1~n，执行堆优化的 Dijkstra算法求解单源最短路径。S一定是第一个被从堆中取出的节点，我们扫描s的所有出边，当扩展、更新完成后，令$dist[s]=+∞$，然后继续求解。当s第二次被从堆中取出时，$diast[s]$就是经过点 s 的最小环长度。
不过我还没有见到相关例题。
喜欢的话，给博主赏一杯冰阔乐吧~
|
|
|
