藏宝图

最小生成树 图论

题面

$ysn$发现了一张奇怪的藏宝图。图上有$n$个点,$m$条无向边。已经标出了图中两两
之间距离$dist$。但是$ysn$知道,只有当图刚好又是一颗树的时候,这张藏宝图才是真的。
如果藏宝图是真的,那么经过点$x$的边的边权平均数最大的那个$x$是藏着宝物的地方。
请计算这是不是真的藏宝图,如果是真的藏宝之处在哪里。

解析

光是判断是不是树就让我想半天。。。
当时我想的是，因为该图联通，所以给的距离中一定只有$n-1$条是边，其它$n^2-n-(n-1)$个距离都是边之和。
而且对于任意两点来说， 边之和 一定大于它们两个的任意一条邻边。(因为 边之和 起码由两条邻边构成）
所以对于任意两点，我们可以优先取相对于 边之和 值更小的邻边,保证了取距离小的边这一操作的正确性。
强上$Kruskal$啊。
然后$O(n^2)$算两点距离（以一个点为根，就可以把到每个点的距离转化为深度）看是否符合来判断树。
接下来随便怎么搞都可以。
考场掉$30pts$缘故：

• $Dat$结构体的边长不开$long\ long$
• 没注意到只有一个点的情况（所以答案变量的初始值要设为可行解）

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define eps 1e-9
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=3000;
ll dis[N][N],d[N];
double mx;
int pos,h[N],n,tot,cnt;
struct Edge{int to,nxt;ll w;}e[N<<1];
il void add(re int u,re int v,re ll w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
struct Dat
{
  int u,v;ll w;
  bool operator < (const Dat &o) const {return w<o.w;}
}a[N*N];
int f[N];
il void dfs(re int u,re int fa,re ll deep)
{
  //printf("%d %d %lld\n",u,fa,deep);
  d[u]=deep;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u,deep+e[i].w);
    }
}
il int check()
{
  fp(i,1,n)
  {
    dfs(i,0,0);
    fp(j,1,n) if(d[j]!=dis[i][j]) return 0;
  }
  return 1;
}
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
int main()
{
  freopen("treas.in","r",stdin);
  freopen("treas.out","w",stdout);
  re int T=gi();
  while(T--)
    {
      n=gi();tot=0;
      fp(i,1,n)
    {
      f[i]=i;
      fp(j,1,n)
        {
          dis[i][j]=gi();
          if(i<j) a[++tot]=(Dat){i,j,dis[i][j]};
        }
    }
      sort(a+1,a+1+tot);
      memset(h,-1,sizeof(h));cnt=0;
      fp(i,1,tot)
    {
      re int u=a[i].u,v=a[i].v,fu=find(u),fv=find(v);ll w=a[i].w;
      //printf("%d %d %d %d %d %lld\n",i,u,v,fu,fv,w);
      if(fu==fv) continue;
      add(u,v,w);add(v,u,w);
      f[fu]=fv;
    }
      if(!check()) {puts("No");continue;}else puts("Yes");
      mx=-1e18;pos=1;
      fp(i,1,n)
    {
      re ll sum=0,ysn=0;
      for(re int j=h[i];j+1;j=e[j].nxt)
        {
          re int v=e[j].to;
          sum+=e[j].w;++ysn;
        }
      if(1.0*sum/ysn+eps>mx) mx=1.0*sum/ysn,pos=i;
    }
      printf("%d\n",pos);
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}