清河哪里做网站,百度推广没有效果怎么办,沈阳城乡建设局官网,网站主机注册题目链接
观光之旅
题目描述
给定一张无向图#xff0c;求图中一个至少包含 3 3 3 个点的环#xff0c;环上的节点不重复#xff0c;并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。
你需要输出最小环的方案#xff0c;若最小环不唯一#xff0c;输出…题目链接
观光之旅
题目描述
给定一张无向图求图中一个至少包含 3 3 3 个点的环环上的节点不重复并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。
你需要输出最小环的方案若最小环不唯一输出任意一个均可。
输入格式
第一行包含两个整数 N N N 和 M M M表示无向图有 N N N 个点 M M M 条边。
接下来 M M M 行每行包含三个整数 u v l uvl uvl表示点 u u u 和点 v v v 之间有一条边边长为 l l l。
输出格式
输出占一行包含最小环的所有节点按顺序输出如果不存在则输出 No solution.。
样例 #1
样例输入 #1
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20样例输出 #1
1 3 5 2提示
【数据范围】 1 ≤ N ≤ 100 1≤N≤100 1≤N≤100, 1 ≤ M ≤ 10000 1≤M≤10000 1≤M≤10000, 1 ≤ l 500 1≤l500 1≤l500
算法思想
根据题目描述求的是无向图中的最小环要求环中至少包含 3 3 3 个节点且环上的节点不重复。当边权都为正数式最小环中的节点一定不会重复否则就不是最小环了如下图所示。 求最小环的长度
无向图的最小环问题可以使用「Floyd」算法解决。基本思想是
当外层循环 k k k刚开始时 d [ i , j ] d[i,j] d[i,j]保存着从节点 i i i到 j j j经过编号不超过 k − 1 k-1 k−1的最短路径长度此时如果引入新节点 k k k构成了环那么环的长度为 d [ i , j ] g [ j ] [ k ] g [ k ] [ i ] d[i,j]g[j][k]g[k][i] d[i,j]g[j][k]g[k][i]如下图所示 那么 m i n { d [ i , j ] g [ j ] [ k ] g [ k ] [ i ] } min\{d[i,j]g[j][k]g[k][i]\} min{d[i,j]g[j][k]g[k][i]}其中 1 ≤ i j k 1\le i\lt j\lt k 1≤ijk就是满足以下两个条件的最小环长度 由编号不超过 k k k的节点构成经过节点 k k k
从 1 ∼ n 1\sim n 1∼n枚举 k k k取上式的最小值就可以得到整张图的最小环长度。
求最小环上的节点
除了计算最小环之外题目还要求记录最小环的上所有节点。当更新最小环时环上的节点包含 i i i、 i i i到 j j j之间最短路上的节点以及 i i i和 k k k。那么如何得到 i i i到 j j j之间最短路上的节点
使用Floyd算法计算最短路时当 d [ i ] [ j ] d [ i ] [ k ] d [ k ] [ j ] d[i][j]d[i][k]d[k][j] d[i][j]d[i][k]d[k][j]时可以更新节点 i i i到 j j j的最短路同时记录节点 i i i到 j j j的最短路是经过 k k k点中转得到的不妨记 p o s [ i , j ] k pos[i,j]k pos[i,j]k。
那么经过节点 i i i到 j j j的最短路径的可以分成两个部分
节点 i i i到 k k k的最短路节点 k k k到 j j j的最短路
可以通过递归的方式分别获取这两部分经过的节点。
时间复杂度
Floyd算法内可以同时求最小环和最短路因此时间复杂度为 O ( n 3 ) O(n^3) O(n3)。
代码实现
#include bits/stdc.h
using namespace std;
const int N 105, INF 0x3f3f3f3f;
int n, m;
int g[N][N], d[N][N];
int pos[N][N];//pos[i][j]表示i和j最短路经过k点中转
vectorint path; //保存最小环路径
void get_path(int i, int j)
{if(pos[i][j] 0) return; //i和j之间不存在中转点int k pos[i][j]; //k是i和j最最短路的中转点get_path(i, k); //递归后取i-k最短路上的节点path.push_back(k);get_path(k, j); //递归后取k-j最短路上的节点
}
int main()
{cin n m;memset(g, 0x3f, sizeof g); //初始化邻接矩阵for(int i 1; i n; i ) g[i][i] 0;while (m -- ){int a, b, c;cin a b c;g[a][b] g[b][a] min(g[a][b], c); //无向图可能存在重边}int ans INF;memcpy(d, g, sizeof d); //初始化最短路for(int k 1; k n; k ){//计算由编号不超过k的节点构成的最小环for(int i 1; i k; i ) //枚举环中的点for(int j i 1; j k; j ){if((long long)d[i][j] g[j][k] g[k][i] ans) //出现更小的环{ans d[i][j] g[j][k] g[k][i];path.clear(); //清除之前的最小环路径path.push_back(k); //k-i-最短路路径-jpath.push_back(i);get_path(i, j);//获取i-j最短路径上的节点path.push_back(j);}}//计算最短路for(int i 1; i n; i )for(int j 1; j n; j )if(d[i][j] d[i][k] d[k][j]){d[i][j] d[i][k] d[k][j];pos[i][j] k; //记录最短路中转点}}if(ans INF) puts(No solution.);else //存在最小环{for(int i : path) cout i ;}
}
