1 条题解
-
0
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
- 上传者