HDOJ 1875 畅通工程再续

资料

最小生成树(MST)讲解请看:
http://www.wutianqi.com/?p=1284


题目传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1875
Prim版本:
31MS 372K 1314 B C++
解答报告:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cmath>
using namespace std;
const int INF = 10000000;
 
double arcs[205][205], dis[205];
int x[205], y[205], vis[205];
int nCases, islands;
int x_tmp, y_tmp, rec;
double tmp, _min;
bool flag;
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &nCases);
 
    while(nCases--)
    {
        scanf("%d", &islands);
        for(int i=0; i<islands; ++i)
            scanf("%d %d", &x[i], &y[i]);
        for(int i=0; i<islands; ++i)
        {
            arcs[i][i] = 0.0;
            for(int j=i+1; j<islands; ++j)
            {
                x_tmp = x[i]-x[j];
                y_tmp = y[i]-y[j];
                tmp = sqrt((double)x_tmp*x_tmp + y_tmp*y_tmp);
                if(tmp<10 || tmp>1000)
                    tmp = INF;
                arcs[i][j] = arcs[j][i] = tmp;
            }
        }
        for(int i=1; i<islands; ++i)
        {
            dis[i] = arcs[0][i];
            vis[i] = 0;
        }
        dis[0] = 0.0;
        vis[0] = 1;
        double res = 0.0;
        for(int i=1; i<islands; ++i)
        {
            _min = INF;
            flag = 0;
            for(int j=0; j<islands; ++j)
                if(!vis[j] && dis[j]<_min)
                {
                    _min = dis[j];
                    rec = j;
                    flag = 1;
                }
            if(!flag)
                break;
            res += _min;
            vis[rec] = 1;
            for(int j=0; j<islands; ++j)
                if(!vis[j] && arcs[rec][j] < dis[j])
                    dis[j] = arcs[rec][j];
        }
        if(flag)
            printf("%.1lf\n", res*100);
        else
            printf("oh!\n");
    }
    return 0;
}
<hr>

Kruskal版本:
187MS 284K 1654 B C++
解答报告:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef struct Road
{
    int c1, c2;
    double cost;
}Road;
 
struct Point
{
    int x, y;
};
 
bool myCompare(const Road &a, const Road &b)
{
    if(a.cost < b.cost)
        return 1;
    return 0;
}
 
Road road[5051];
Point point[101];
int city[101];
 
int Find(int n)
{
    if(city[n] == -1)
        return n;
    return city[n] = Find(city[n]);
}
 
bool Merge(int s1, int s2)
{
    int r1 = Find(s1);
    int r2 = Find(s2);
    if(r1 == r2)
        return 0;
    if(r1 < r2)
        city[r2] = r1;
    else
        city[r1] = r2;
    return 1;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    int nCases;
    scanf("%d", &nCases);
    while(nCases--)
    {
        scanf("%d", &n);
        for(int i=0; i<n; ++i)
            scanf("%d %d", &point[i].x, &point[i].y);
        int m = 0;
        for(int i=0; i<n; ++i)
            for(int j=0;j<i;j++)
             {
                 road[m].c1 = i;
                 road[m].c2 = j;
                 road[m].cost=sqrt(double((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)));
                 m++;
             }
        memset(city, -1, sizeof(city));
        sort(road, road+m, myCompare);
        int count = 0;
        double sum = 0.0;
        for(int i=0; i<m; ++i)
        {
            if(road[i].cost<=1000 && road[i].cost>=10 && Merge(road[i].c1, road[i].c2))// ??????
            {
                count ++;
                sum += road[i].cost;
            }
            if(count == n-1)
                break;
        }
        if(count == n-1)
            printf("%.1lf\n", sum*100);
        else
            puts("oh!");
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1875 畅通工程再续》有4个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注