HDU 1875 畅通工程再续最小生成树

思路：

题目给的是每个小岛的坐标，俩个岛之间的距离等于俩个岛之间的欧几里得距离，然后套用P算法或者K算法就好了。用K算法或者P算法都可以，但是这道题显然需要计算出来每俩个岛之间的距离，这样就有接近V^2/2条边，输入稠密图，所以用P算法会更好点。注意的是题目中说两个岛之间的距离不能大于1000米也不能小于10米，如果用P算法那么如果俩个岛之间的距离不符合条件就把这个到之间的距离设置为无穷大，如果用的是K算法只需要在合并俩个点时，判断下符合条件再合并就好了，并注意控制K算法时的边数，体重没有显式的给出边数。

以下是C++的代码K算法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int MAXN = 1e2+ 3;
int pre[MAXN];
int n;

struct Node
{
    int u, v;
    double w;
}cy[MAXN  * MAXN];

struct P
{
    double x;
    double y;
}p[MAXN ];

int Find(int x)
{
   int r = x;
   while(pre[r] != r)
   {
       r = pre[r];
   }
   int i = x, j;
   while(pre[i] != r)
   {
       j = pre[i];
       pre[i] = r;
       i = j;
   }
   return r;
}

double dx(P a, P b)
{
    return hypot(a.x - b.x, a.y - b.y);
}

int mycmp(Node a,Node b)
{
    return a.w < b.w;
}

void mst()
{
    for(int i = 0 ; i < 102; i++)
        pre[i] = i;
}

double kru(int l)
{
    double ans = 0;
    int cnt = 0;
    for(int i = 1; i <= l; i++)
    {
        int fv = Find(cy[i].v);
        int fu = Find(cy[i].u);
        if(fv != fu)
        {
            if(cy[i].w < 10 || cy[i].w > 1000) continue;
            pre[fv] = fu;
            ans += cy[i].w;
            cnt ++;
        }
        if(cnt == n -1)
        {
            return ans;
        }
    }
    return -1;
}

int main()
{
    //freopen("in.cpp","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        mst();
        for(int i = 1; i <= n ;i++)
        {
            scanf("%lf%lf",&p[i].x, &p[i].y);
        }
        int l = 1;
        for(int i = 1; i< n; i++)
        {
            for(int j = i + 1; j <= n; j++)
            {
                cy[l].u = i;
                cy[l].v = j;
                cy[l].w = dx(p[i], p[j]);
                l++;
            }
        }
        sort(cy + 1,cy + l + 1, mycmp);
        double ans = kru(l);
        if(ans != -1)
            printf("%.1lf
",ans * 100);
        else
            printf("oh!
");
    }
    return 0;
}

Java版的P算法

 1 import java.util.Scanner;
 2 import java.util.Comparator;
 3 import java.util.Arrays;
 4 import java.text.DecimalFormat;
 5 
 6 class Node{
 7     int x, y;
 8 }
 9 
10 public class Main{
11     final static int MAXN = 100 + 3;
12     final static int INF = 0x3f3f3f3f - 1;
13     static double[][] edge = new double[ MAXN ][ MAXN ];
14     static double[] lowcost = new double[ MAXN ];
15     static int[] used = new int[ MAXN ];
16     static Node[] vg = new Node[ MAXN ];
17     public static void main( String[] args ){
18         Scanner sc = new Scanner( System.in );
19         int t = sc.nextInt();
20         while( ( t-- ) != 0 ){
21             int c = sc.nextInt();
22             for( int i = 1; i <= c; i++ ){
23                 vg[ i ] = new Node();
24                 vg[ i ].x = sc.nextInt();
25                 vg[ i ].y = sc.nextInt();
26             }
27             for( int i = 1; i <= c; i++ ){
28                 for( int j = i + 1; j <= c; j++ ){
29                     edge[ i ][ j ] =  edge[j ][ i ] = ( dxy( vg[i], vg[j] ) < 10) || (dxy( vg[i], vg[j] ) > 1000 ) ?  INF + 1 : dxy( vg[i], vg[j]) ;
30                 }
31                 edge[ i ][ i ] = INF + 1;
32             }
33             double ans = prim( c , 1 );
34             if( ans == -1 ) System.out.println( "oh!" );
35             else {
36                 ans *= 100;
37                 DecimalFormat df = new DecimalFormat("0.0");
38                 System.out.println( df.format(ans) );
39             }
40         }
41         sc.close();
42     }
43     public static double dxy( Node a, Node b ){
44         return Math.sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
45     }
46     public static double prim( int n, int sta ){
47         for( int i = 1; i <= n; i++ ){
48             used[ i ] = 0;
49             lowcost[i] = edge[ sta ][ i ];
50         }
51         used[ sta ] = 1;
52         int cnt = 0;
53         double ans = 0;
54         for( int i = 1; i < n; i ++ ){
55             int index = -1;
56             double mini = (double) INF;
57             for( int j = 1; j <= n; j++ ){
58                 if( used[ j ] == 0 && lowcost[ j ] < mini ){
59                     mini = lowcost[ j ];
60                     index = j;
61                 }
62             }
63             if( index != -1){
64                 used[ index ] = 1;
65                 cnt++;
66                 ans += lowcost[ index ];
67                 for(int j = 1; j <= n; j++ ){
68                     if( used[ j ] == 0 && lowcost[ j ] > edge[ index ][ j ] ){
69                         lowcost[ j ] = edge[ index ][ j ];
70                     }    
71                 }
72             }
73         }
74         if( cnt == n - 1 ) return ans;
75         return -1;
76     }
77 }

HDU 1875 畅通工程再续 最小生成树

HDU 1875 畅通工程再续最小生成树