1 条题解

  • 0
    @ 2025-2-14 21:30:05

    C++ :

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int n,k,a[101][101],dis[101],sum=0,tot=0;
    void work(int);
    int main()
    {
    	memset(a,0x7f,sizeof(a));
    	cin>>n>>k;
    	int x,y,t;
    	for(int i=1;i<=k;i++)
    	{
    		cin>>x>>y>>t;
    		a[x][y]=a[y][x]=t;
    		tot+=t;
    	}
    	work(1);
    	cout<<tot-sum;
    }
    void work(int x)
    {
    	for(int i=1;i<=n;i++) dis[i]=a[x][i];
    	dis[x]=0;
    	for(int j=1;j<=n;j++)
    	{
    		int k,mi=0x7f7f7f7f;
    		for(int i=1;i<=n;i++)
    		{
    			if(dis[i]<mi&&dis[i]!=0)
    			{
    				mi=dis[i];
    				k=i;
    			}
    		}
    		sum+=dis[k];
    		dis[k]=0;
    		for(int i=1;i<=n;i++)
    		{
    			if(dis[i]>a[k][i]) dis[i]=a[k][i];
    		}
    	}
    }
    

    Pascal :

    program wtc;
    type
     list=record
      frontv,endv,w:longint;
      end;
    var
     n,i,j,s1,s2,k,p,q,min:longint;
     a:array[1..100,1..100]of longint;
     c:array[1..100]of list;
     t:list;
    procedure prim;
    begin
     for i:= 1 to n-1 do
      begin
       c[i].frontv:=1;
       c[i].endv:=i+1;
       c[i].w:=a[c[i].frontv,c[i].endv];
      end;
     for k:= 1 to n-1 do
      begin
       min:=maxint;
       for i:=k to n-1 do
        if min>c[i].w then
         begin
          min:=c[i].w;
          p:=i;
         end;
       t:=c[p]; c[p]:=c[k]; c[k]:=t;
       j:=c[k].endv;
       for i:= k+1 to n-1 do
        begin
         if a[j,c[i].endv]<c[i].w then
          begin
           c[i].w:=a[j,c[i].endv];
           c[i].frontv:=j;
          end;
        end;
      end;
    end;
    
    begin
     readln(n,k);
     for i:= 1 to k do
       begin
        read(p,q);
        read(a[p,q]);
        a[q,p]:=a[p,q];
        s1:=s1+a[p,q];
       end;
     for i:= 1 to n do
      for j:= 1 to n do
        if (i<>j) and (a[i,j]=0) then
         a[i,j]:=maxint;
       prim;
       s2:=0;
     for i:= 1 to n-1 do
      s2:=s2+c[i].w;
      writeln(s1-s2);
    end.
    
    • 1

    信息

    ID
    944
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者