# 最小生成树C代码

gjwin 0 2016-03-05 10:58 0

### 基本信息

× 1    × 1

4

```#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = int(1e9);
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 200 + 10;
int T,n,m,cnt,p[maxn],kase=0;
double ans[maxn][maxn],x[maxn],y[maxn];
struct node {
int a, b;
double dist;
node(int a=0, int b=0, double dist=0):a(a), b(b), dist(dist) {}
bool operator < (const node& rhs) const {
return dist < rhs.dist;
}
}a[maxn*maxn];
vector<node> g[maxn];
int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); }
void dfs(int u, int fa) {
int len = g[u].size();
for(int i=0;i<len;i++) {
int v = g[u][i].a;
if(v != fa) {
ans[1][v] = max(ans[1][u], g[u][i].dist);
dfs(v, u);
}
}
}
double solve() {
for(int i=1;i<=n;i++) p[i] = i, g[i].clear();
sort(a, a+cnt);
for(int i=0;i<cnt;i++) {
int x = _find(a[i].a);
int y = _find(a[i].b);
if(x != y) {
p[x] = y;
g[a[i].a].push_back(node(a[i].b, 0, a[i].dist));
g[a[i].b].push_back(node(a[i].a, 0, a[i].dist));
}
}
ans[1][1] = -1.0;
dfs(1, 1);
return ans[1][2];
}
int main() {
while(~scanf("%d",&n) && n) {
for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
cnt = 0;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
double cur = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
a[cnt++] = node(i,j,cur);
}
}
printf("Scenario #%d\n",++kase);
printf("Frog Distance = %.3f\n\n",solve());
}
return 0;
}```

14评论:
• anasilvabr 2018-05-09 07:35 代码数：0

Valuable information. Thank you for always posting quality content.

Curso de Excel Completo

• ossaa 2018-05-09 16:46 代码数：0

This is such a great resource that you are providing and you give it away for free.

cryptocurrency converter calculator

• ossaa 2018-05-10 19:23 代码数：0

This is such a great resource that you are providing and you give it away for free. I love seeing websites that understand the value of providing a quality resource for free. It is the old what goes around comes around routine.

• ossaa 2018-05-16 20:00 代码数：0

I recently came across your blog and have been reading along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.

SEO Company

• hellojukay 2016-07-12 12:48 代码数：0

这是c++代码

• gererik 2018-04-21 14:21 代码数：0

Thanks  for another wonderful post. Where else could anybody get that type of info in such an ideal way of writing? ninja logo

• gererik 2018-04-21 15:34 代码数：0

Keep up the good  work , I read few posts  on this  web site  and I  conceive that your blog  is very   interesting and has   sets  of  fantastic   information. refrigerator repair service near me

• herenzi 2017-07-15 00:17 代码数：0

一次性包含这么多头文件，用到了几个？

• 认识你自己 2017-07-25 21:40 代码数：0

66666

• gererik 2018-04-23 16:49 代码数：0

This is such a great resource that you are providing and you give it away for free. community   community