首页 > 代码库 > 1863
1863
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<vector> 5 #include<map> 6 #include<set> 7 #include<cstring> 8 #include<cstdio> 9 #include<cmath> 10 #include<cstdlib> 11 #include<stack> 12 #include<iomanip> 13 #include<cctype> 14 #include<climits> 15 #include<queue> 16 using namespace std; 17 typedef long long ll; 18 typedef unsigned long long ull; 19 20 const int maxn=5010; 21 22 int fa[maxn],u[maxn],v[maxn],w[maxn],r[maxn]; 23 24 void init(int m,int n) 25 { 26 for(int i=1;i<=m;i++) 27 r[i]=i; 28 for(int i=1;i<=n;i++) 29 fa[i]=i; 30 } 31 32 int cmp(int i,int j) 33 { 34 return w[i]<w[j]; 35 } 36 37 int find(int x) 38 { 39 return fa[x]==x?x:fa[x]=find(fa[x]); 40 } 41 42 43 int main() 44 { 45 int m,n,ans,num; 46 while(~scanf("%d %d",&m,&n)){ 47 if(m==0) 48 return 0; 49 init(m,n); 50 for(int i=1;i<=m;i++) 51 scanf("%d%d%d",&u[i],&v[i],&w[i]); 52 sort(r+1,r+m+1,cmp); 53 num=ans=0; 54 for(int i=1;i<=m;i++){ 55 int e=r[i]; 56 int x=find(u[e]); 57 int y=find(v[e]); 58 if(x!=y){ 59 ans+=w[e]; 60 fa[x]=y; 61 } 62 } 63 for(int i=1;i<=n;i++) 64 if(i==fa[i]) 65 num++; 66 if(num>1) 67 printf("?\n"); 68 else 69 printf("%d\n",ans); 70 } 71 return 0; 72 }
1863
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。