package graph.Floyd;

/**
 * https://blog.csdn.net/qq_30277239/article/details/107702663
 * 给定一张无向图，求图中一个至少包含3个点的环，环上的节点不重复，并且环上的边的长度之和最小。
 * 该问题称为无向图的最小环问题。
 * 你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。
 * 输入格式
 * 第一行包含两个整数N和M，表示无向图有N个点，M条边。
 * 接下来M行，每行包含三个整数u，v，l，表示点u和点v之间有一条边，边长为l。
 * 输出格式
 * 输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出’No solution.’。
 * 数据范围
 * 1≤N≤100,
 * 1≤M≤10000,
 * 1≤l<500
 * 输入样例：
 * 5 7
 * 1 4 1
 * 1 3 300
 * 3 1 10
 * 1 2 16
 * 2 3 100
 * 2 5 15
 * 5 3 20
 * 输出样例：
 * 1 3 5 2
 * 如图所示，设环上编号最大的节点编号是k，i和j分别是环上与k相邻的两个节点。根据之前对floyd算法的推导，f[k][i][j]表示图上i经过编号不超过k的节点到达j的最短路径长度，观察上图可以发现，环的长度等于i到j的最短距离加上g[i][k]再加上g[k][j]，设环的长度为ans，则ans = f[i][j] + g[i][k] + g[k][j]，这里的f[i][j]是对f[k-1][i][j]降维后的结果，为什么是f[k-1][i][j]而不是f[k][i][j]，因为前面已经规定k是最大的节点，环上其他的节点必然都小于k。为什么要这么规定，这种思路是如何来的？后面会分析这种思路的由来。
 *
 * 我们知道，floyd算法最外层k刚刚循环到第k次时，f[i][j]存储的还是i经过编号不超过k-1的节点到达j的最短路径长度，此时的f[i][j]正是我们所需要的，因此在第k次循环开始时，由k，i，j加上i到j中间的节点构成的最小环长度就是f[i][j] + g[i][k] + g[k][j]，我们还是用三层循环去枚举所有的情况，最终就可以求出最小环的长度。
 */
public class 最小环 {
    public static void main(String[] args) {

    }
}