题解

给你平面上若干点，生成一颗完全图，让你生成一颗最小生成树。模板题。图中已经有了的边要将权值置0。代码是队友写的。

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define INF 1000000005#define eps 1e-10#define PI acos(-1.0)#define K (0.017453292519943295769236907684886l)#define LL long long#define ULL unsigned long longusing namespace std;const int maxn = 755;double a[maxn][maxn], dist[maxn];int n, pre[maxn], m, x[maxn], y[maxn], vis[maxn][maxn], flag[maxn];double Get_dist(int s, int t){ return sqrt((x[s] - x[t]) * (x[s] - x[t]) + (y[s] - y[t]) * (y[s] - y[t]));}int main(){ scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) a[i][j] = Get_dist(i, j); scanf("%d", &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); vis[u][v] = vis[v][u] = 1; a[u][v] = a[v][u] = 0; } for (int i = 1; i <= n; i++) { flag[i] = 1; dist[i] = a[1][i]; pre[i] = 1; } flag[1] = 0; pre[1] = 0; for (int i = 1; i < n; i++) { double minx = 1e30; int p; for (int j = 1; j <= n; j++) if (flag[j] && minx > dist[j]) { minx = dist[j]; p = j; } if (!vis[p][pre[p]]) printf("%d %d\n", p, pre[p]); flag[p] = 0; for (int j = 1; j <= n; j++) if (dist[j] > a[p][j]) { dist[j] = a[p][j]; pre[j] = p; } } return 0;}