题目描述：
给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。
数据范围：
$1\le n \le 100, 1\le m \le 5\times 10^3,1\le d \le 10^5$
题解：
如果用环上点的最大编号对环进行标识，那么刚好对应floyd算法。floyd算法的最外层循环枚举的是中转点，可以把它作为最大的点。floyd保证了最外层遍历到 $k$ 时，已经求出以 $[0,k-1]$ 为中间点的最短路径。假设在某个环中最大编号为 $L$ ，那么在floyd算法外层遍历到 $L$ 时，已经得到 $x,y$ 之间不包含 $L$ 的最短路。这时，如果加上 $(L,x)(L,y)$ 就可以得到一个经过 $x,y,L$ 的环。求最小环的话，每次更新最小值即可。
注意枚举环的循环，需要枚举 $[0,k-1]$ 中的 $x,y$ ，然后因为需要求至少包含3个点的环，所以 $x\ne y$ .这个地方相加可能会溢出，需要注意不能使用0x3f。也可以全转成 long long。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e2 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int g[maxn][maxn];
int dp[maxn][maxn];
int ans;
void solve()
{
ans = INF;
for (int k = 1; k <= n; ++k)
{
for (int i = 1; i < k; ++i)
{
for (int j = 1; j < k; ++j)
{
if (i != j)
ans = min(1ll * ans, 1ll * dp[i][j] + g[i][k] + g[k][j]);
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
dp[j][i] = dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
read(n, m);
memset(g, 0x3f, sizeof(g));
memset(dp, 0x3f, sizeof(dp));
for (int i = 1, u, v, w; i <= m; ++i)
{
read(u, v, w);
g[u][v] = g[v][u] = min(w, g[u][v]);
dp[u][v] = dp[v][u] = g[u][v];
}
solve();
if (ans == INF)
cout << "No solution." << endl;
else
cout << ans << endl;
return 0;
}
|