Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
貌似写得不是很好#include "iostream" #include "algorithm" using namespace std; int low_point[27]; int map[30][30]; int old_p[27]; int num; void init(){ int i,j; for(i=0;i<27;i++) low_point[i]=-1; for(i=0;i<27;i++) old_p[i]=0; for(i=0;i<30;i++) for(j=0;j<30;j++) map[i][j]=-1; } int prim(){ int v1,v2; int n=1; int min,cost=0; int i,j,k; low_point[1]=1; old_p[1]=1; for(i=1;i<num;i++){ min=101; v2=0; v1=0; for(j=1;j<=n;j++){ for(k=1;k<27;k++){ if(map[low_point[j]][k]>-1 && min>map[low_point[j]][k] && !old_p[k]){ min=map[low_point[j]][k]; v2=k; v1=low_point[j]; } } } cost+=min; low_point[++n]=v2; old_p[v2]=1; } return cost; } int main(){ cin>>num; int i,m,n1; char c,c1; int n; while(num){ init(); n1=num; while(--n1){ cin>>c>>n; for(i=1;i<=n;i++) { cin>>c1>>m; map[c-'A'+1][c1-'A'+1]=m; map[c1-'A'+1][c-'A'+1]=m; } } cout<<prim()<<endl; cin>>num; } return 0; } /* 9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0 216 30 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator