首页 > 代码库 > bzoj1083题解

bzoj1083题解

2024-09-12 06:50:34   215人阅读

【题意分析】

　　给你一张无向图，求其最小瓶颈生成树的值。

【解题思路】

　　有一个很显然的定理：任意一张无向图的最小生成树即为最小瓶颈生成树。所以求最小生成树的时候取边权的最大值即可。

　　或者可以修改Dijkstra算法，dis[i]表示当前i离最小瓶颈生成树的最小瓶颈值，也可以证明是具有最优子结构的。

　　复杂度最低O(nlog2n)。

【参考程序】

技术分享
 1 #pragma GCC optimize(2) 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #define REP(i,low,high) for(register int i=(low);i<=(high);i++) 6 using namespace std; 7 template<typename T> inline bool getmin(T &tar,const T &pat) {return pat<tar?tar=pat,1:0;} 8 template<typename T> inline bool getmax(T &tar,const T &pat) {return pat>tar?tar=pat,1:0;} 9 bool usd[310]; int n,m,dst[310],edg[310][310];10 int main()11 {12     memset(dst,0x7f,sizeof dst),memset(edg,0x7f,sizeof edg),memset(usd,0,sizeof usd),dst[1]=0;13     for(scanf("%d%d",&n,&m);m--;) {int u,v,w; scanf("%d%d%d",&u,&v,&w); edg[u][v]=edg[v][u]=w;}14     REP(times,1,n)15     {16         int i=0; REP(j,1,n) if(!usd[j]&&dst[j]<dst[i]) i=j; usd[i]=1;17         REP(j,1,n) if(!usd[j]) getmin(dst[j],max(dst[i],edg[i][j]));18     }19     int ans=0; REP(i,1,n) getmax(ans,dst[i]);20     return printf("%d %d\n",n-1,ans),0;21 }
View Code

 

bzoj1083题解


联系
我们