题目描述

Czy爬上黑红树，到达了一个奇怪的地方……

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

 

输入

输入数据第一行一个数T,表示T组数据。

对于每组数据，第一行一个n，表示藏宝图上的点的个数。

接下来n行,每行n个数，表示两两节点之间的距离。

 

输出

输出一行或两行。第一行”Yes”或”No”，表示这是不是真的藏宝图。

若是真的藏宝图，第二行再输出一个数，表示哪个点是藏宝之处。

 

样例输入

230 7 97 0 29 2 030 2 72 0 97 9 0

样例输出

Yes1Yes3样例解释:第一棵树的形状是1--2--3。1、2之间的边权是7，2、3之间是2。 第二棵树的形状是2--1--3。2、1之间的边权是2，1、3之间是7。

提示

对于30%数据，n<=50,1<=树上的边的长度<=10^9。

对于50%数据，n<=600.

对于100%数据，1<=n<=2500,除30%小数据外任意0<=dist[i][j]<=10^9,T<=5

【题解】

        考试的时候完全没有思路，想试试把多余边都拆掉能不能行，但是完全没有想起“最小生成树”这几个字眼。其实想想最小生成树，加有用的边不就相当于删无用的边吗？还是得懂得变通啊。

       稠密图卡克鲁斯卡尔是众所周知，而每两点之间都有边可算得上是最稠密不过的图了，复习普里姆，选择最近的点把它加入树。建出树之后dfs求各点到1的距离，lca求各两点之间距离，验证一下是否是树。是树不是树都好办，这题主要是步骤非常多，用了很多算法，调试有一定难度(我也不出意料地打得非常冗长)。思路上大概也只有最小生成树和稠密图比较困难吧。

 

#include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;const int sj=2505;ll ca,n,dist[sj][sj],dis[sj],mi;int e,xb[sj],lca[sj][sj],f[sj],zx,h[sj],fa[sj];bool r[sj],op;void init(){     scanf("%d",&n);     memset(dis,0x3f,sizeof(dis));     memset(f,-1,sizeof(f));     memset(h,-1,sizeof(h));     memset(r,0,sizeof(r));     for(int i=1;i<=n;i++)     {       for(int j=1;j<=n;j++)         scanf("%lld",&dist[i][j]);     }}struct B{     int ne,v,w;}b[sj*2];void add(int x,int y,int z){     b[e].v=y;     b[e].ne=h[x];     b[e].w=z;     h[x]=e++;}void mst(){     memset(dis,0x3f,sizeof(dis));     for(int i=1;i<=n;i++)       if(dist[i][1]
          
           mi)            {               mi=temp;               zx=i;            }          }          printf("%d\n",zx);      }    }    //while(1);    return 0;}