poj 2485 Highways (最小生成树)

这题挺无语啊，在poj上交c++就wrong,用cin输入就会TLE;

看来以后要交G++,用scanf输入了

题意：求最小生成树的边的最长边

 1 #include <iostream>
 2  #include<cstdio>
 3  #include<cstring>
 4  #include<cstdlib>
 5  #include<stack>
 6  #include<queue>
 7  #include<cmath>
 8  #include<algorithm>
 9  using namespace std;
10  int bin[510];
11  struct node
12  {
13      int u,v,w;
14  } q[251000];
15  bool cmp(node x,node y)
16  {
17      return x.w<y.w;
18  }
19  int find(int a)
20  {
21      if(a==bin[a])
22          return a;
23      else
24          bin[a]=find(bin[a]);
25  }
26  int main()
27  {
28      int t,i,j,n,num,p,m;
29      int x,y;
30      int cnt;
31      scanf("%d",&t);
32      while(t--)
33      {
34          scanf("%d",&n);
35          num=0; m=n*n;
36          for(i=1; i<=n; i++)
37              bin[i]=i;
38          p=0;
39          for(i=1; i<=n; i++)
40              for(j=1; j<=n; j++)
41              {
42                  q[p].u=i;  q[p].v=j;
43                  scanf("%d",&q[p].w);
44                  p++;
45              }
46          sort(q,q+m,cmp);
47          for(i=0; i<m; i++)
48          {
49              x=find(q[i].u);
50              y=find(q[i].v);
51              if(x!=y)
52              {
53                  num++;
54                  bin[x]=y;
55              }
56              if(num==n-1)
57              {
58                  cnt=q[i].w;//因为排完序了，所以最后一个就是最大的
59                  break;
60              }
61          }
62          cout<<cnt<<endl;
63      }
64  }
65  
66