1 条题解
-
0
C++ :
#include<cstdlib> #include<iostream> #include<vector> #include<algorithm> using namespace std; int n,m; struct node{ int i; int j; int k; }; bool compare(node q,node w){ return q.k<w.k; } int main(){ cin>>n>>m; int i,j,k,p; int * dataset=(int *)malloc(sizeof(int) * n); node * nodes=(node *)malloc(sizeof(node) * m); for(p=0;p<n;p++) dataset[p]=0; for(int p=0;p<m;p++){ cin>>i>>j>>k; node a={i,j,k}; nodes[p]=a; } sort(nodes,nodes+m,compare); int count=0; int max; for(int p=0;p<m;p++){ if(dataset[nodes[p].i-1]==0||dataset[nodes[p].j-1]==0){ count++; dataset[nodes[p].i-1]=1; dataset[nodes[p].j-1]=1; max=nodes[p].k; } } cout<<count<<" "<<max<<endl; }
Pascal :
var i,n,m,ans,root1,root2:longint; elen,eu,ev,father:array[0..10001]of longint; procedure qsort(l,r:longint); var i,j,temp,mid:longint; begin i:=l; j:=r; mid:=elen[(l+r) div 2]; repeat while elen[i]<mid do inc(i); while elen[j]>mid do dec(j); if i<=j then begin temp:=elen[i];elen[i]:=elen[j];elen[j]:=temp; temp:=eu[i];eu[i]:=eu[j];eu[j]:=temp; temp:=ev[i];ev[i]:=ev[j];ev[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; function getfather(x:longint):longint; begin if father[x]=x then exit(x); father[x]:=getfather(father[x]); exit(father[x]); end; begin readln(n,m); for i:=1 to m do readln(eu[i],ev[i],elen[i]); qsort(1,m); ans:=0; for i:=1 to n do father[i]:=i; for i:=1 to m do begin root1:=getfather(eu[i]); root2:=getfather(ev[i]); if root1<>root2 then begin father[root1]:=root2; inc(ans); if ans=n-1 then begin ans:=elen[i];break; end; end; end; write(n-1,' ',ans); end.
- 1
信息
- ID
- 983
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者