1875.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<cstdio>
#include<cmath>
#include<string>
const double MAX = 0x7fffffff;
struct node
{
    double x, y;
}island[110];
int num;
double hash[110][110];
bool visit[110];
double calcu(int a, int b)
{
    return sqrt((island[a].x - island[b].x) * (island[a].x - island[b].x)  + (island[a].y - island[b].y) * (island[a].y - island[b].y));
}
void dfs(int k)
{
    visit[k] = true;
    int i;
    for(i = 0; i < num; i++)
        if(hash[k][i] != -1 && visit[i] == false)
            dfs(i);
}
double prime()
{
    double min = MAX, sum = 0;
    int i_index, j_index, i, j, ca;
    bool pass[110];
    memset(pass, false, sizeof(pass));
    for(i = 0; i < num; i++)
        for(j = 0; j < num; j++)
                if(hash[i][j] != -1 && i != j && hash[i][j] < min)
                {
                    min = hash[i][j];
                    i_index = i;
                    j_index = j;
                }
	pass[i_index] = true;
    pass[j_index] = true;
    sum += min;
    for(ca = 1; ca < num; ca++){
		min = MAX;
        for(i = 0; i < num; i++)
			for(j = 0; j < num; j++)
				if(pass[i] == true && pass[j] == false && hash[i][j] != -1 && i != j && min > hash[i][j])
                {
					min = hash[i][j];
                    j_index = j;
                }
        if(min < MAX)
			sum += min;
		pass[j_index] = true;
    }
    return sum;
}
int main()
{
    int test, i, j;
    bool isliant;
    scanf("%d", &test);
    while(test--)
    {
        memset(hash, 0, sizeof(hash));
        memset(island, 0, sizeof(island));
        memset(visit, false, sizeof(visit));
        scanf("%d", &num);
        for(i = 0; i < num; i++)
            scanf("%lf %lf", &island[i].x, &island[i].y);

        for(i = 0; i < num; i++)
            for(j = 0; j < num; j++)
            {
                hash[i][j] = calcu(i, j);
                if(hash[i][j] < 10 || hash[i][j] > 1000)
                {
                    hash[i][j] = -1;
                }
                else
                {
                    hash[i][j] *= 100;
                }
            }
        dfs(0);
        isliant = true;
        for(i = 0; i < num; i++)
            if(visit[i] == false)
            {
                isliant = false;
                break;
            }
        if(isliant == false)
            printf("oh!\n");
        else
            printf("%.1lf\n", prime());
    }
	return 0;
}