【題目描述】：

給定一張無向圖，求圖中一個至少包含 3個點的環，環上的節點不重復，并且環上的邊的長度之和最小。該問題稱為無向圖的最小環問題。在本題中，你需要輸出最小環的邊權之和。若無解，輸出 “No solution.”。圖的節點數不超過 100。
【輸入描述】：

第一行兩個正整數 n,m表示點數和邊數。

接下來 m行，每行三個正整數 x,y,z，表示節點 x,y之間有一條長度為 z的邊。
【輸出描述】：

輸出一個最小環的邊權之和。若無解，輸出 “No solution.”
【樣例輸入】：

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

【樣例輸出】：

61

【時間限制、數據范圍及描述】：

時間：1s 空間：512M

對于 20%的數據：1<=n<=10；

對于100%的數據：1<=n<=100；邊權<=300。

題解：emmm換了個oo，就從90變成100了哈哈。

代碼：

#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int N=105,oo=1<<28; int f[N][N],ans=oo,r[N][N],x,y,z,n,m; int main(){freopen("276.in","r",stdin);freopen("276.out","w",stdout);scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=1<<28;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)r[i][j]=1<<28;for(int i=1;i<=m;i++){scanf("%d %d %d",&x,&y,&z);if(f[x][y]>z) f[x][y]=f[y][x]=r[x][y]=r[y][x]=z;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){ans=min(ans,r[i][k]+r[k][j]+f[i][j]);}}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);}if(ans==oo) printf("No solution.");else printf("%d\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/wuhu-JJJ/p/11123485.html

總結

以上是生活随笔為你收集整理的【UOJ 276】无向图最小环的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。