首页 > 代码库 > bzoj1083题解
bzoj1083题解
【题意分析】
给你一张无向图，求其最小瓶颈生成树的值。
【解题思路】
有一个很显然的定理：任意一张无向图的最小生成树即为最小瓶颈生成树。所以求最小生成树的时候取边权的最大值即可。
或者可以修改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 }
bzoj1083题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。