1 条题解

  • 0
    @ 2025-2-21 19:54:32

    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
    上传者