1 solutions

  • 0
    @ 2025-11-5 19:33:39

    C :

    #include<stdio.h>
    int main()
    {
    	int a[105][105],v[105]={0},dis[105]={0};
    	int i,j,t,n,min,node,sum=0;
    	scanf("%d",&n);
    	for (i=0;i<n;i++)
    		for (j=0;j<n;j++)
    			scanf("%d",&a[i][j]);
    	v[0]=1;
    	for (i=0;i<n;i++)
    		dis[i]=a[0][i];
    	for (i=1;i<n;i++)
    	{
    		node=-2;
    		min=100000;
    		for (j=1;j<n;j++)
    		{
    			if (v[j]==0 && dis[j]<min)
    			{
    				min=dis[j];
    				node=j;
    			}
    		}
    		v[node]=1;
    		sum+=min;
    		for (j=1;j<n;j++)
    		{
    			if (v[j]==0 && dis[j]>a[node][j])
    				dis[j]=a[node][j];
    		}
    	}
    	printf("%d\n",sum);
    	return 0;
    }
    
    
    
    

    C++ :

    #include<stdio.h>
    int cost[560][560];
    int use[56];
    int dd[560][560];
    int mincost[560];
    int min(int a,int b)
    {
        return a>b?b:a;
    }
    int main()
    {
    	
    	int n;
    	int v,i,j;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<n;j++)
    		{
    			scanf("%d",&v);
    			if(dd[i][j]==0)
    			{
    		    		cost[i][j]=v;
    	               cost[j][i]=v;
    				   dd[i][j]=1;
    				   dd[j][i]=1;
    			}
    			else
    			{
    				if(cost[i][j]>v)
    				{
    					cost[i][j]=v;
    					cost[j][i]=v;
    				}
    			}
    		}
    		
    	}
    	
    	
    	
    	for(i=0;i<n;i++)
    	{
    		use[i]=0;
    		mincost[i]=10000000;
    	}
    	mincost[0]=0;
    	int res=0;
    	while(1)
    	{
    		int p=-1;
    		for(i=0;i<n;i++)
    		{
    			//printf("\n");
    			if(use[i]==0&&(p==-1||mincost[i]<mincost[p]))
    			{// printf("%d  %d  %d %d\n",mincost[i],mincost[p],i,p);
    				p=i;
    				//printf("%d  %d  %d %d\n",mincost[i],mincost[p],i,p);
    			}
    		}
    		if(p==-1)
    		{
    			break;
    		}
    		use[p]=1;
    		res+=mincost[p];
    		for(i=0;i<n;i++)
    		{
    			mincost[i]=min(mincost[i],cost[p][i]);
    		}
            //  for(i=0;i<n;i++)
            //  {
            //      printf("%d ",mincost[i]);
            //  }
            //  printf("\n");
    		
    	}
    	printf("%d\n",res);
     
    
    return 1;
    }
    

    Pascal :

    //codeless;
    
    type
      hugeint=record
       fromv,endv,weight:longint;
    end;
    var elist:array[1..10001] of hugeint;
        g:array[1..500,1..500] of longint;
        cost:array[1..101,1..101] of longint;
         n,i,j,ans:longint;
    procedure prim;
    var w,min,m,s,i,j,k:longint;
     t:hugeint;
    begin
     for i:=1 to n-1 do
      begin
       elist[i].fromv:=1;
       elist[i].endv:=i+1;
       elist[i].weight:=g[1,i+1];
      end;
     for k:=1 to n-1 do
      begin
       min:=maxlongint;
       m:=k;
       for j:=k to n-1 do
        if elist[j].weight<min then begin
         min:=elist[j].weight;
         m:=j;
         end;
         inc(ans,min);
      if m<>k then begin
       t:=elist[k];
       elist[k]:=elist[m];
       elist[m]:=t;
       end;
      j:=elist[k].endv;
      for i:=k+1 to n-1 do
       begin
        s:=elist[i].endv;
        w:=g[j,s];
        if (w<elist[i].weight) and (w<>maxlongint) then
         begin
          elist[i].weight:=w;
          elist[i].fromv:=j;
         end;
       end;
      end;
    end;
    
    begin
    //assign(input,'agrinet.in');
    //assign(output,'agrinet.out');
    //reset(input);
    //rewrite(output);
    readln(n);
    
    for i:=1 to n do
     for j:=1 to n do
      begin
       read(cost[i,j]);
      if cost[i,j]>0 then
       g[i,j]:=cost[i,j]
       else g[i,j]:=maxlongint;
      end;
    prim;
    writeln(ans);
    
    
    // close(input);
    // close(output);
    end.
    
    
    • 1

    Information

    ID
    19390
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By