首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 4081 (次小生成树变形)

HDU 4081 (次小生成树变形)

作者头像
Ch_Zaqdt
发布2019-01-10 15:55:16
4570
发布2019-01-10 15:55:16
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4081

       题意是有n个点,分别输入n个点的坐标和这个点的权值,然后要给这些点建边,建边的权值就是两点间的距离,现在可以免费的建一条边,求免费建边的两个点的权值和与总费用的最大值。

       思路就是类比次小生成树的思路,在删边的过程中维护所要求的最大值就好了。


AC代码:

#include <bits/stdc++.h>
#define maxn 1005
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
  int x,y,w;
}Edge[maxn];
double Map[maxn][maxn], path[maxn][maxn];
bool vis[maxn], used[maxn][maxn];
double dist[maxn];
int pre[maxn];
int T,n,m;

void init(){
  memset(used, false, sizeof(used));
  memset(path, 0, sizeof(path));
  memset(Map, inf, sizeof(Map));
}

double dis(int x,int y,int x1,int y1){
  double xx = (x - x1) * (x - x1) + (y - y1) * (y - y1);
  return sqrt(xx);
}

double Prim(){
  memset(vis, false, sizeof(vis));
  double sum = 0;
  for(int i=1;i<=n;i++){
    dist[i] = Map[1][i];
    pre[i] = 1;
  }
  vis[1] = true;
  for(int i=1;i<n;i++){
    double Min = inf;
    int u = 1;
    for(int j=1;j<=n;j++){
      if(!vis[j] && dist[j] < Min){
        Min = dist[j];
        u = j;
      }
    }
    vis[u] = true;
    sum += Min;
    used[ u ][ pre[u] ] = used[ pre[u] ][ u ] = true;
    for(int j=1;j<=n;j++){
      if(vis[j] && j != u)
        path[j][u] = path[u][j] = max(path[j][pre[u]], dist[u]);
      if(vis[j] == false){
        if(dist[j] > Map[u][j]){
          dist[j] = Map[u][j];
          pre[j] = u;
        }
      }
    }
  }
  return sum;
}

double SecPrim(double xx){
  double ans = -1;
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      if(used[i][j] == true){
        ans = max(ans, (Edge[i].w + Edge[j].w) / (xx - Map[i][j]));
      }
      else{
        ans = max(ans, (Edge[i].w + Edge[j].w) / (xx - path[i][j]));
      }
    }
  }
  return ans;
}

int main()
{
  scanf("%d",&T);
  while(T--){
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
      scanf("%d%d%d",&Edge[i].x,&Edge[i].y,&Edge[i].w);
    }
    for(int i=1;i<=n;i++){
      Map[i][i] = 0;
      for(int j=i+1;j<=n;j++){
        Map[i][j] = Map[j][i] = dis(Edge[i].x, Edge[i].y, Edge[j].x, Edge[j].y);
      }
    }
    double ans = Prim();
    double ans1 = SecPrim(ans);
    printf("%.2lf\n", ans1);
  }
  return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年01月07日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

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