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

为什么都说kruskal是低空掠过,我422ms过啊

Posted by sqc1999 at 2015-06-07 19:53:13 on Problem 3625
上代码,请大家看看
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>

using namespace std;

struct Edge
{
	int from, to;
	double pow;
	Edge(int from, int to, double pow) :from(from), to(to), pow(pow) {}
	bool operator<(const Edge &e) const { return pow < e.pow; }
};

typedef pair<int, int> pii;
pii p[1001];
int f[1001];
vector<Edge> e;

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

double getdis(const pii &a, const pii &b) { return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2)); }

int main()
{
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i].first >> p[i].second;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			e.push_back(Edge(i, j, getdis(p[i], p[j])));
		}
	}
	sort(e.begin(), e.end());
	for (int i = 1; i <= n; i++) f[i] = i;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		int xx = find(x), yy = find(y);
		if (xx != yy) f[xx] = yy;
	}
	double ans = 0;
	for (int i = 0; i < e.size(); i++)
	{
		int x = find(e[i].from), y = find(e[i].to);
		if (x != y)
		{
			f[x] = y;
			ans += e[i].pow;
		}
	}
	cout.setf(ios::fixed);
	cout << setprecision(2) << ans;
}

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