HDOJ 1863 prim算法 HDOJ 1879

 1 #include<cstdio>
 2 #include<cstring>
 3 #define inf 0xffffff
 4 int g[101][101];
 5 int ans;
 6 void prim(int n)
 7 {
 8     int lowcost[101],used[101],i,j,k,min,closet[101];
 9     memset(used,0,sizeof(used));
10     for(i=1;i<=n;i++)
11         lowcost[i]=g[i][1],closet[i]=1;
12     used[1]=1;
13     for(i=1;i<n;i++)
14     {
15         j=1;
16         min=inf;
17         for(k=2;k<=n;k++)
18         {
19             if(lowcost[k]<min&&!used[k])
20                 min=lowcost[k],
21                 j=k;
22         }
23         ans+=g[j][closet[j]];
24         used[j]=1;
25         for(k=2;k<=n;k++)
26         {
27             if(g[k][j]<lowcost[k]&&!used[k])
28                 lowcost[k]=g[k][j],
29                 closet[k]=j;
30         }
31     }
32 
33 }
34 int main()
35 {
36     int m,n;
37     while(scanf("%d %d",&m,&n)!=EOF&&m)
38     {
39         int i,j;
40         ans=0;
41         for(i=1;i<=n;i++)
42             for(j=1;j<=n;j++)
43                 g[i][j]=inf;
44         int a,b,t;
45         for(i=1;i<=m;i++)
46         {
47             scanf("%d %d %d",&a,&b,&t);
48             if(g[a][b]>t)
49                 g[a][b]=g[b][a]=t;
50         }
51         if(m<n-1)
52             printf("?
");
53         else
54         {
55            prim(n);
56            if(ans>=inf)
57                printf("?
");
58            else
59                printf("%d
",ans);
60         }
61     }
62 
63     return 0;
64 }

View Code

9896382

2013-12-26 16:56:48

Accepted

1863

0MS

296K

989 B

C++

泽泽

1879

9896417

2013-12-26 17:03:42

Accepted

1879

234MS

300K

934 B

C++

泽泽

 1 #include<cstdio>
 2 #include<cstring>
 3 #define inf 0xffffff
 4 int g[101][101];
 5 int ans;
 6 void prim(int n)
 7 {
 8     int lowcost[101],used[101],i,j,k,min,closet[101];
 9     memset(used,0,sizeof(used));
10     for(i=1;i<=n;i++)
11         lowcost[i]=g[i][1],closet[i]=1;
12     used[1]=1;
13     for(i=1;i<n;i++)
14     {
15         j=1;
16         min=inf;
17         for(k=2;k<=n;k++)
18         {
19             if(lowcost[k]<min&&!used[k])
20                 min=lowcost[k],
21                 j=k;
22         }
23         ans+=g[j][closet[j]];
24         used[j]=1;
25         for(k=2;k<=n;k++)
26         {
27             if(g[k][j]<lowcost[k]&&!used[k])
28                 lowcost[k]=g[k][j],
29                 closet[k]=j;
30         }
31     }
32 
33 }
34 int main()
35 {
36     int n;
37     while(scanf("%d",&n)!=EOF&&n)
38     {
39         int i,j;
40         ans=0;
41         for(i=1;i<=n;i++)
42             for(j=1;j<=n;j++)
43                 g[i][j]=inf;
44         int a,b,t;
45         for(i=1;i<=n*(n-1)/2;i++)
46         {
47             scanf("%d %d %d %d",&a,&b,&t,&j);
48             if(g[a][b]>t&&j==0)
49                 g[a][b]=g[b][a]=t;
50             else if(j==1)
51                 g[a][b]=g[b][a]=0;
52         }
53         prim(n);
54         printf("%d
",ans);
55     }
56 
57     return 0;
58 }

View Code