首页 > 代码库 > poj2485
poj2485
找最小生成树里面最长的边是多少,还是用kruskal做的。。
#include<iostream> #include<algorithm> using namespace std; int father[501]; struct n1 { int s,e,w; }; n1 path[30000]; bool cmp(n1 a,n1 b) { return a.w<b.w; } int find(int i) { while(father[i]!=i) { i=father[i]; } return i; } int kruskal(int v,int e) { int temp1,temp2,i,max1,num_bian; for(i=1;i<=v;i++) { father[i]=i; } sort(path+1,path+e+1,cmp); i=max1=num_bian=0; v--; while(num_bian!=v) { i++; temp1=find(path[i].s); temp2=find(path[i].e); if(temp1!=temp2) { max1=max(path[i].w,max1); num_bian++; if(temp1>temp2) { temp1^=temp2^=temp1^=temp2; } father[temp2]=temp1; } } return max1; } int main() { int t,i,j,k,map[501][501],n; scanf("%d",&t); while(t--) { scanf("%d",&n); k=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&map[i][j]); if(j>i) { k++; path[k].s=i; path[k].e=j; path[k].w=map[i][j]; } } printf("%d\n",kruskal(n,k)); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。