[补档]藏宝图

藏宝图

题目

codeforces472D加强版，原题传送门：http://codeforces.com/problemset/problem/472/D

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

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

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

　INPUT

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

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

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

OUTPUT

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

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

SAMPLE

INPUT

0 7 9

7 0 2

9 2 0

0 2 7

2 0 9

7 9 0

OUTPUT

Yes

解题报告

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

正解：

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

这里需要注意的是，kruskal会被卡，要用prim （人题目给你矩阵还强行用kruskal也是醉），虽然突然不会prim了- -

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

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  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]<dis1[k])
 48                 k=j;
 49         vis[k]=1;
 50         for(L j=1;j<=n;j++)
 51             if(!vis[j]&&dis[k][j]<dis1[j])
 52                 dis1[j]=dis[k][j],fa[j]=k;
 53     }
 54 }
 55 inline void build(){
 56     for(L i=2;i<=n;i++){
 57         insert(i,fa[i],dis1[i]);
 58         insert(fa[i],i,dis1[i]);
 59         degree[i]++,degree[fa[i]]++;
 60     }
 61 }
 62 inline void dfs(L start,L now,L fa,L deep){
 63     for(L i=pre[now];i!=-1;i=a[i].n){
 64         L e(a[i].e);
 65         if(e==fa)
 66             continue;
 67         dis2[start][e]=deep+a[i].w;
 68         dfs(start,e,now,deep+a[i].w);
 69         num[now]+=a[i].w;
 70         num[e]+=a[i].w;
 71     }
 72 }
 73 inline bool judge(){
 74     for(L i=1;i<=n;i++)
 75         for(L j=1;j<=n;j++)
 76             if(i!=j)
 77                 if(dis[i][j]!=dis2[i][j]&&dis2[i][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
",ans);
115     }
116 }

View Code