poj 1751 输出MST中新加入的边

给出结点的坐标以及已建好的边要输出MST中加入的边(已建好的边就不用输出了)
结点的编号从1开始
注意这题只有一组数据不能用多组输入否则就超时（在这被坑惨了Orz）

Sample Input

9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2
Sample Output

1 6
3 7
4 9
5 7
8 3

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 const int INF=0x3f3f3f3f;
10 const int MAXN=760;
11 bool vis[MAXN];
12 double lowc[MAXN];
13 int n ;
14 double cost[MAXN][MAXN] ;
15 int pre[MAXN] ;
16 
17 struct poin
18 {
19     int x ;
20     int y ;
21 }p[MAXN];
22 
23 void Prim()
24 {
25     memset(vis,false,sizeof(vis));
26     vis[1]=true;
27     for(int i=2;i<=n;i++)
28     {
29         lowc[i]=cost[1][i];
30         pre[i] = 1 ;
31     }
32 
33     for(int i=2;i<=n;i++)
34     {
35         double minc=INF;
36         int p=-1;
37         for(int j=1;j<=n;j++)
38             if(!vis[j]&&minc>lowc[j])
39             {
40                 minc=lowc[j];
41                 p=j;
42             }
43             if(minc != 0)
44                 {
45                     printf("%d %d
",pre[p],p);
46                 }
47             if (p == -1)
48                return ;
49             vis[p]=true;
50             for(int j=1;j<=n;j++)
51                 if(!vis[j]&&lowc[j]>cost[p][j])
52                     {
53                         lowc[j]=cost[p][j];
54                         pre[j]=p;
55                     }
56     }
57     return ;
58 }
59 
60 int main()
61 {
62 
63     //freopen("in.txt","r",stdin) ;
64         scanf("%d" , &n) ;
65         int i , j ;
66         for (i = 1 ; i <= n ; i++)
67             scanf("%d %d" , &p[i].x , &p[i].y) ;
68         for (i = 1 ; i <= n ; i++)
69         {
70             cost[i][i] = INF ;
71             for (j = i+1 ; j <= n ; j++)
72             {
73                 double t = sqrt((double)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y)) ;
74                 cost[i][j] = t ;
75                 cost[j][i] = t ;
76             }
77         }
78 
79         int m , u , v ;
80         scanf("%d" , &m) ;
81         while(m--)
82         {
83             scanf("%d %d" , &u , &v) ;
84             cost[u][v] = 0 ;
85             cost[v][u] = 0 ;
86         }
87         Prim() ;
88 
89 
90     return 0 ;
91 }

View Code