1 solutions
-
0
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