求解!!!过第一个!!!
查看原帖
求解!!!过第一个!!!
402158
c17757822363楼主2022/8/4 15:51
#include <bits/stdc++.h>
using namespace std;
int n,m,f[5000100],cnt,tot;
double ans;
struct kk
{
  int u,v;
  double d;
} edge[5000100];
struct ll
{
  int x,y;
} zb[5000100];
double js(int x,int y)
{
  double a,b;
  a=(double)(zb[x].x-zb[y].x)*(double)(zb[x].x-zb[y].x);
  b=(double)(zb[x].y-zb[y].y)*(double)(zb[x].y-zb[y].y);
  return (double)sqrt(a+b);
}
int find(int x)
{
  if(f[x]==x) return x;
  else return f[x]=find(f[x]);
}
int read()
{
  int t=0,f=1;
  char a=getchar();
  for(; !isdigit(a); a=getchar())	
    if(a=='-')
      f=-1;
  for(; isdigit(a); a=getchar())
    t=a-'0';
  return t*f;
}
void add(int x,int y,double z)
{
  edge[++tot].u=x;
  edge[tot].v=y;
  edge[tot].d=z;
}
bool cmp(kk x,kk y)
{
  return x.d<y.d;
}
void kruskal()
{
  int x,y;
  for(int i=1; i<=tot; i++)
  {
    x=find(edge[i].u);
    y=find(edge[i].v);
    if(x!=y)
    {
      f[x]=y;
      ans+=edge[i].d;
      cnt++;
    }
    if(cnt==n-1) break;
  }
}
int main()
{
  int x,y;
  n=read();
  m=read();
  for(int i=1; i<=n; i++) f[i]=i;
  for(int i=1; i<=n; i++)
  {
    zb[i].x=read();
    zb[i].y=read();
  }
  for(int i=1; i<=n; i++)
  {
  	for(int j=i+1; j<=n; j++)
    {
      double z=js(i,j);
      add(i,j,z);
    }
  }
    
  for(int j=1; j<=m; j++)
  {
    x=read();
    y=read();
    add(x,y,0.0);
  }
  sort(edge+1,edge+tot+1,cmp);
  kruskal();
  printf("%.2lf", ans);
  return 0;
}
2022/8/4 15:51
加载中...