| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么都说kruskal是低空掠过,我422ms过啊上代码,请大家看看
#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator