首页 > ACM题库 > HDU-杭电 > HDU 3405-World Islands-最小生成树-[解题报告]HOJ
2014
03-23

HDU 3405-World Islands-最小生成树-[解题报告]HOJ

World Islands

问题描述 :

Dubai is a haven for the rich. The government of Dubai finds a good way to make money. They built a lot of artificial islands on the sea and sell them. These islands are shaped into the continents of the world, so they are called “world islands”. All islands are booked out now. The billionaires who buy these islands wants to make friends with each other, so they want these islands all be connected by bridges. Bill Gates also has booked an island, but he is the only one who doesn’t want his island to be connected with other islands, because he prefer to travel on the sea on his old landing craft which is used in the Invasion of Normandy in World War II. Fortunately, Bill doesn’t care about which island is saved for him, so Dubai government can still find the best way to build the bridges. The best way means that the total length of the bridges is minimum. In a word, if there are n islands, what they should do is to build n�2 bridges connecting n-1 islands, and give the rest island to Bill Gates. They can give any island to Bill Gates. Now they pay you good money to help them to find out the best way to build the bridges.
Please note;
1.An island can be considered as a point.
2.A bridge can be considered as a line segment connecting two islands.
3.A bridge connects with other bridges only at the islands.

输入:

The first line is an integer indicating the number of test cases.
For each test case, the first line is an integer n representing the number of islands.(0<n<50)
Then n lines follow. Each line contains two integers x and y( -20 <= x, y <= 20 ) , indicating the coordinate of an island.

输出:

The first line is an integer indicating the number of test cases.
For each test case, the first line is an integer n representing the number of islands.(0<n<50)
Then n lines follow. Each line contains two integers x and y( -20 <= x, y <= 20 ) , indicating the coordinate of an island.

样例输入:

2
5
0 0
1 0
18 0
0 1
1 1
3
0 0
1 0
0 1

样例输出:

3.00
1.00

求删点后最小的生成树,n<50.。。。数据好弱,直接暴力枚举就行。。。删点的时候直接g[i][j]=INF就行了。

#include<iostream>
#include<algorithm>
#include<fstream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(i=a; i<b; i++)
#define FD(i, a, b) for(i=a; i>b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define LL long long
#define CPY(a, b) memcpy(a, b, sizeof(b))
using namespace std;
ofstream fout ("output.txt");
ifstream fin ("input.txt");

const int maxn = 100;
const double INF = 222222;
int T, n;
double g[maxn][maxn], low[maxn], x[maxn], y[maxn], tmp[maxn][maxn];
bool vis[maxn];

double prim(int start)
{
    double  min, res=0;
    int i, j, pos;
    CLR(vis, 0);
    vis[start] = 1; pos = start;
    FF(i, 1, n+1)   if(i!=pos) low[i] = g[pos][i];
    FF(i, 1, n)
    {
        min = INF;
        FF(j, 1, n+1)
            if(vis[j] == 0 && min > low[j])
                min = low[j], pos = j;
        res += min;
        vis[pos] = 1;
        FF(j, 1, n+1)
            if(vis[j] == 0 && low[j] > g[pos][j])
                low[j] = g[pos][j];
    }
    return res;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int i, j;
        scanf("%d", &n);
        FF(i, 1, n+1)  scanf("%lf%lf", &x[i], &y[i]);
        FF(i, 1, n+1)
            FF(j, 1, n+1)
                g[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
        double ans = INF*INF;
        FF(i, 1, n+1)
        {
            CPY(tmp, g);
            FF(j, 1, n+1)
            {
                g[i][j] = g[j][i] = INF;
            }
            ans = min(ans, prim(1));
            CPY(g, tmp);
        }
        printf("%.2lf\n", n < 3 ? 0 : ans-INF);
    }
    return 0;
}

参考:http://blog.csdn.net/diary_yang/article/details/9318159


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?