最小环问题
最小环就是指在一张图中找出一个环,使得这个环上的各条边的权值之和最小。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 const int maxn=9999; 6 int n,m,u,v,w,ans,g[maxn][maxn],dis[maxn][maxn]; 7 8 int main(){ 9 cin>>n>>m; 10 for(int i=1;i<=n;i++)//初始化 11 for(int j=1;j<=n;j++) 12 g[i][j]=maxn; 13 for(int i=1;i<=m;i++){//双向图 14 cin>>u>>v>>w; 15 g[u][v]=w; 16 g[v][u]=w; 17 } 18 for(int i=1;i<=n;i++) 19 for(int j=1;j<=n;j++) 20 dis[i][j]=g[i][j]; 21 ans=maxn; 22 for(int k=1;k<=n;k++){//Floyed算法 23 for(int i=1;i<=n-1;i++){ 24 for(int j=i+1;j<=n-1;j++){ 25 ans=min(ans,dis[i][j]+g[i][k]+g[k][j]);//找最小值 26 } 27 } 28 for(int i=1;i<=n;i++){//松弛 29 for(int j=1;j<=n;j++){ 30 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 31 } 32 } 33 } 34 cout<<ans<<endl; 35 return 0; 36 }