poj 2395 Out of Hay

最小生成树方法与最短路径有些相似，多数题又可用并查集求解，但并查集比较耗时，解决某些稍复杂的问题可能超时；

View Code

 1 //poj2395
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define M 1000000001
 5 #define N 2500
 6 int map[N][N],a[N],b[N];
 7 int n,m;
 8 int met()
 9 {
10     int i,k,flag,min;
11     for(i=1;i<=n;i++)
12     {
13         a[i]=map[1][i];
14     }
15     b[1]=1;
16     while(1)
17     {
18         flag=1;min=M;
19         for(i=2;i<=n;i++)
20             if(b[i]==0&&a[i]<min)
21             {
22                 min=a[i];flag=0;
23                 k=i;
24             }
25             if(flag)
26                 break;
27             b[k]=1;
28             for(i=2;i<=n;i++)
29                 if(b[i]==0&&a[i]>map[k][i])
30                     a[i]=map[k][i];
31     }
32      min=0;
33         for(i=2;i<=n;i++)
34             if(min<a[i])
35                 min=a[i];
36     return min;
37 }
38 
39 
40 int main()
41 {
42     int i,j;
43     int x,y,z;
44     scanf("%d%d",&n,&m);
45         
46         for(i=1;i<=n;i++)
47         {
48             for(j=1;j<=n;j++)
49                 map[i][j]=M;
50         }
51         
52         for(i=1;i<=n;i++)
53             map[i][i]=0;
54         memset(b,0,sizeof(b));
55         for(i=1;i<=m;i++)
56         {
57             scanf("%d%d%d",&x,&y,&z);
58             if(map[x][y]>z)//没这句话 ，就WA，郁闷好久
59             map[x][y]=map[y][x]=z;
60         }
61         
62             printf("%d\n",met());
63 
64     return 0;
65 }