题解 P6175 【无向图的最小环问题】
珈乐唯毒
2020-05-21 10:08:40
本题应该使用floyd算法
~~（因为标签里有呢）~~
算法思路：在Floyd算法的计算过程中，我们可以取小于k的两个节点i,j。若i,j与k之间均有边，则存在一个可能的最小环 i-j-k (因为i,j之间的路径长度为只经过1-(k-1)号节点的最短路径)。
代码如下：
```
#include<bits/stdc++.h>
using namespace std;
int n,m,s,a,b,w;
int d[1005][1005],g[1005][1005],ans;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)d[i][j]=10000000;
ans=10000000;
for(int i=1;i<=m;i++){
cin>>a>>b>>w;
if(a==b)continue;
if(g[a][b]==0)g[a][b]=w;
g[a][b]=min(g[a][b],w);
g[b][a]=g[a][b];
d[a][b]=g[a][b];
d[b][a]=g[a][b];//存无向图
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j&&g[i][k]>0&&g[k][j]>0)ans=min(ans,d[i][j]+g[i][k]+g[k][j]);
if(d[i][k]+d[k][j]<d[i][j])d[i][j] = d[i][k]+d[k][j];
}
}
}
if(ans!=10000000)cout<<ans;
else cout<<"No solution.";
return 0;
}
```