藏宝图

题目

codeforces472D加强版，原题传送门：

本题在原题基础上加了一问，然而就是这一问把我搞炸了= =

 

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

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

　INPUT

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

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

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

OUTPUT

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

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

SAMPLE

INPUT

2

3

0 7 9

7 0 2

9 2 0

3

0 2 7

2 0 9

7 9 0

OUTPUT

Yes

1

Yes

3

解题报告

考试时只打出了第一问，还是O(n³)的复杂度，自然爆了零= =

正解：

首先我们考虑第一问，我们有了每两两点之间的距离，并想办法用其判断这个图是否是一棵树，我们想，在一棵树中，每两点之间路径是唯一的，故路径长度即为路径所经过所有边的长度之和,那么我们利用所给距离建出最小生成树，假如该图为树，那么最小生成树即为本身，假如不是，那么两点间距离一定会有变化，这些利用dfs什么的就可以做到了，顺便还可以建成图。

这里需要注意的是，kruskal会被卡，要用prim

（人题目给你矩阵还强行用kruskal也是醉），虽然突然不会prim了- -

接下来是第二问，那就很简单了- -，建完图，一求边权平均数就可以了

1 #include
       
          2 #include
        
           3 #include
         
            4 using namespace std;  5 typedef long long L;  6 inline L read(){  7     L sum(0);  8     char ch(getchar());  9     for(;ch<'0'||ch>'9';ch=getchar()); 10     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 11     return sum; 12 } 13 struct edge{ 14     L s,e,n; 15     L w; 16 }a[6001]; 17 L pre[2501],tot; 18 inline void insert(L s,L e,L w){ 19     a[++tot].s=s; 20     a[tot].e=e; 21     a[tot].w=w; 22     a[tot].n=pre[s]; 23     pre[s]=tot; 24 } 25 L T,n; 26 L dis[2501][2501],dis1[2501],dis2[2501][2501]; 27 L fa[2501]; 28 bool vis[2501]; 29 L degree[2501]; 30 double num[2501]; 31 inline void clear(){ 32     tot=0; 33     memset(pre,-1,sizeof(pre)); 34     memset(dis,0,sizeof(dis)); 35     memset(dis1,0x7f,sizeof(dis1)); 36     memset(dis2,0,sizeof(dis2)); 37     memset(fa,0,sizeof(fa)); 38     memset(vis,0,sizeof(vis)); 39     memset(degree,0,sizeof(degree)); 40     memset(num,0,sizeof(num)); 41 } 42 inline void prim(){ 43     dis1[1]=0; 44     for(L i=1;i<=n;i++){ 45         L k(0); 46         for(L j=1;j<=n;j++) 47             if(!vis[j]&&dis1[j]
          
           0) 78                     return false; 79     return true; 80 } 81 int main(){ 82 //  freopen("1.in","r",stdin); 83 //  freopen("1.out","w",stdout); 84     T=read(); 85     while(T--){ 86         clear(); 87         n=read(); 88         for(L i=1;i<=n;i++){ 89             for(L j=1;j<=n;j++) 90                 dis[i][j]=read(); 91             dis[i][i]=0x7fffffff; 92         } 93         if(n==1){ 94             puts("Yes"); 95             puts("1"); 96             continue; 97         } 98         prim(); 99         build();100         for(L i=1;i<=n;i++)101             dfs(i,i,-1,0);102         if(!judge()){103             puts("No");104             continue;105         }106         puts("Yes");107         double mx(0);108         L ans(0);109         for(L i=1;i<=n;i++){110             num[i]/=(double)degree[i];111             if(num[i]>mx)112                 mx=num[i],ans=i;113         }114         printf("%d\n",ans);115     }116 }