前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最小生成树C代码

最小生成树C代码

原创
作者头像
大师级码师
修改2021-09-22 10:51:14
4980
修改2021-09-22 10:51:14
举报
文章被收录于专栏:大师级码师大师级码师

细节参见代码:

代码语言:javascript
复制
#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[maxnmaxn];
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;
}</pre> 

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档