Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Maybe it can help you

Posted by khesoem at 2010-06-28 21:00:15 on Problem 3625
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;

int n, m, par[1000 + 10], rank[1000 + 10];
vector<pair<double, pair<int, int> > >e;
pair<int, int>p[1000 + 10];

void init(){
	for(int i = 1; i <= n; i++){
		par[i] = i;
		for(int j = i + 1; j <= n; j++){
			e.push_back(make_pair(sqrt((p[j].first - p[i].first) * (p[j].first - p[i].first) + (p[j].second -
			p[i].second) * (p[j].second - p[i].second)), make_pair(i, j)));
		}
	}
	sort(e.begin(), e.end());
}

int findpar(int x){
	if(par[x] == x){
		return x;
	}
	return par[x] = findpar(par[x]);
}

void join(int x, int y){
	int fx = findpar(x), fy = findpar(y);
	if(fx == fy){
		return;
	}
	if(rank[fx] > rank[fy]){
		par[fy] = fx;
	}
	else if(rank[fy] > rank[fx]){
		par[fx] = fy;
	}
	else if(rank[fy] == rank[fy]){
		par[fx] = fy;
		rank[fy]++;
	}
}

double kruskal(){
	double ret = 0;
	for(int i = 0; i < e.size(); i++){
		if(findpar(e[i].second.first) != findpar(e[i].second.second)){
			ret += e[i].first;
			join(e[i].second.first, e[i].second.second);
		}
	}
	return ret;
}

main(){
	scanf("%lld %lld", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%lld %lld", &p[i].first, &p[i].second);
	}
	init();
	for(int i = 0; i < m; i++){
		int x, y;
		scanf("%lld %lld", &x, &y);
		join(x, y);
	}
	printf("%.2f\n", kruskal());
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator