藏宝图

背景
Czy 爬上黑红树，到达了一个奇怪的地方……
题目描述
Czy 发现了一张奇怪的藏宝图。图上有n 个点，m 条无向边。已经标出了图中两两之
间距离dist。但是czy 知道，只有当图刚好又是一颗树的时候，这张藏宝图才是真的。如
果藏宝图是真的，那么经过点x 的边的边权平均数最大的那个x 是藏着宝物的地方。请计
算这是不是真的藏宝图，如果是真的藏宝之处在哪里。
格式
输入数据第一行一个数T,表示T 组数据。
对于每组数据，第一行一个n，表示藏宝图上的点的个数。
接下来n 行,每行n 个数，表示两两节点之间的距离。
输出一行或两行。第一行”Yes”或”No”，表示这是不是真的藏宝图。
若是真的藏宝图，第二行再输出一个数，表示哪个点是藏宝之处。
样例输入
230
7 9
7 0 2
9 2 0

0 2 7
2 0 9
7 9 0
样例输出
Yes
1
Yes
3
样例解释:第一棵树的形状是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

solution：

树的性质：有n个点，n-1条边。

给的矩阵不是树，就是图

先跑一边最小生成树，再用O(n^2)求出最小生成树上各点之间的距离，得到一个新的矩阵

再将新得到的矩阵与原来的进行对比，如果不同，说明是图

至于最小生成树，这题卡kruskar的O(n^2*logn)，用prim O(n^2)

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<cmath>
  5 #include<algorithm>
  6 #define ll long long
  7 #define mem(a,b) memset(a,b,sizeof(a))
  8 #define dd double
  9 using namespace std;
 10 int read()
 11 {
 12     int ans=0;char q=getchar();
 13     while(q<'0'||q>'9')q=getchar();
 14     while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();}
 15     return ans;
 16 }
 17 
 18 int T;
 19 int n;
 20 ll a[2505][2505];
 21 ll d[2505];
 22 int vis[2505],qian[2505];
 23 ll a2[2505][2505];
 24 struct son1
 25 {
 26     int v,next;
 27     ll w;
 28 };
 29 son1 a1[10001];
 30 int first[10001],e;
 31 void addbian(int u,int v,ll w)
 32 {
 33     a1[e].w=w;
 34     a1[e].v=v;
 35     a1[e].next=first[u];
 36     first[u]=e++;
 37 }
 38 
 39 void clear()
 40 {
 41     mem(d,0x7f);
 42     mem(first,-1);
 43     e=0;
 44     mem(a1,0);
 45     mem(a2,0);
 46     mem(vis,0);
 47     mem(qian,0);
 48 }
 49 
 50 void dfs(int fa,int x,int now)
 51 {
 52     for(int i=first[x];i!=-1;i=a1[i].next)
 53     {
 54         int temp=a1[i].v;
 55         if(temp==fa)continue;
 56         a2[now][temp]=a2[now][x]+a1[i].w;
 57         dfs(x,temp,now);
 58     }
 59 }
 60 
 61 void out11()
 62 {
 63     printf("

");
 64     for(int i=1;i<=n;++i)
 65       printf("%d ",qian[i]);
 66     printf("

");
 67     for(int i=1;i<=n;++i)
 68       printf("%d ",d[i]);
 69     printf("

");
 70     for(int i=1;i<=n;++i)
 71     {
 72         for(int j=1;j<=n;++j)
 73           printf("%d ",a[i][j]);
 74         printf("
");
 75     }
 76     printf("
");
 77     for(int i=1;i<=n;++i)
 78     {
 79         for(int j=1;j<=n;++j)
 80           printf("%lld ",a2[i][j]);
 81         printf("
");
 82     }
 83     printf("
");
 84 }
 85 
 86 int main(){
 87     //freopen("1.txt","r",stdin);
 88     //freopen("treas1.in","r",stdin);
 89     //freopen("treas.out","w",stdout);
 90     T=read();
 91     while(T--)
 92     {
 93         int wrong=0;
 94         scanf("%d",&n);
 95         for(int i=1;i<=n;++i)
 96           for(int j=1;j<=n;++j)
 97             scanf("%lld",&a[i][j]);
 98             //a[i][j]=read();
 99         
100         for(int i=1;i<=n;++i)
101           if(a[i][i])wrong=1;
102         
103         for(int i=1;i<=n;++i)
104           for(int j=i+1;j<=n;++j)
105             if(a[i][j]!=a[j][i])
106               wrong=1;
107         
108         if(wrong)
109         {printf("No
");continue;}
110         
111         clear();
112         
113         d[1]=0;
114         
115         for(int i=1;i<=n;++i)
116         {
117             int k=0;
118             for(int j=1;j<=n;++j)
119               if(!vis[j]&&d[j]<d[k])
120                 k=j;
121             
122             //printf("k=%d
",k);
123             
124             vis[k]=1;
125             for(int j=1;j<=n;++j)
126               if(!vis[j]&&a[k][j]<d[j])
127               {
128                     //printf("j=%d
",j);
129                     qian[j]=k;
130                 d[j]=a[k][j];
131                 }
132         }
133         
134         for(int i=2;i<=n;++i)
135           addbian(i,qian[i],d[i]),addbian(qian[i],i,d[i]);
136         
137         for(int i=1;i<=n;++i)
138             dfs(-1,i,i);
139         
140         //out11();
141         
142         for(int i=1;i<=n;++i)
143         {
144             if(wrong==1)break;
145           for(int j=1;j<=n;++j)
146             if(a[i][j]!=a2[i][j])
147             {wrong=1;break;}
148         }
149         
150         if(wrong)
151         {printf("No
");continue;}
152         
153         dd maxl=0;
154         int order;
155         for(int i=1;i<=n;++i)
156         {
157             dd sum=0;int ci=0;
158             for(int j=first[i];j!=-1;j=a1[j].next)
159             {sum+=a1[j].w;++ci;}
160             sum/=(dd)ci;
161             //printf("i=%d sum=%.4lf
",i,sum);
162             if(sum>maxl){maxl=sum;order=i;}
163         }
164         
165         
166         printf("Yes
%d
",order);
167     }
168     //while(1);
169     return 0;
170 }

正解

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 #define ll long long
  8 #define mem(a,b) memset(a,b,sizeof(a))
  9 #define dd double
 10 using namespace std;
 11 struct son
 12 {
 13     int v,next;
 14     ll w;
 15 };
 16 son a1[50001];
 17 int first[50001],e;
 18 
 19 void addbian(int u,int v,int w)
 20 {
 21     a1[e].w=w;
 22     a1[e].v=v;
 23     a1[e].next=first[u];
 24     first[u]=e++;
 25 }
 26 
 27 struct son1
 28 {
 29     int order;
 30     ll val;
 31 };
 32 son1 v[2505][2505];
 33 bool ok(son1 a,son1 b)
 34 {
 35     return a.val<b.val;
 36 }
 37 
 38 int T,n;
 39 int now[2505];
 40 ll a[2505][2505];
 41 bool flag[2505];
 42 ll quan[2505];
 43 int fa[2505];
 44 
 45 void dfs(int x)
 46 {
 47     flag[x]=1;
 48     //printf("x=%d
",x);
 49     while(now[x]<=n)
 50     {
 51         while(flag[v[x][now[x]].order])++now[x];
 52         if(now[x]>n)return ;
 53         int temp=v[x][now[x]].order;
 54         int www=v[x][now[x]].val;
 55         if(a[x][temp]>a[fa[x]][temp]){++now[x];continue;}
 56         addbian(x,temp,www);
 57         addbian(temp,x,www);
 58         quan[temp]=www;
 59         fa[temp]=x;
 60         dfs(temp);
 61     }
 62 }
 63 
 64 /*void out11()
 65 {
 66     printf("
");
 67     for(int i=1;i<=n;++i)
 68     {
 69         printf("i=%d
",i);
 70         for(int j=first[i];j!=-1;j=a1[j].next)
 71             printf("%d %d
",a1[j].v,a1[j].w);
 72     }
 73     printf("
");
 74 }*/
 75 
 76 void clear()
 77 {
 78     mem(fa,0);
 79     mem(quan,0);
 80     mem(first,-1);
 81     mem(a1,0);
 82     e=0;
 83     mem(flag,0);
 84 }
 85 
 86 int main(){
 87     //freopen("treas.in","r",stdin);
 88     //freopen("treas.out","w",stdout);
 89     //freopen("1.txt","r",stdin);
 90     scanf("%d",&T);
 91     while(T--)
 92     {
 93         clear();
 94         for(int i=0;i<2505;++i)now[i]=2;
 95         scanf("%d",&n);
 96         for(int i=1;i<=n;++i)
 97           for(int j=1;j<=n;++j)
 98             {scanf("%lld",&a[i][j]);v[i][j].val=a[i][j];v[i][j].order=j;}
 99         for(int i=1;i<=n;++i)sort(v[i]+1,v[i]+1+n,ok);
100         //cout<<0;
101         //bfs();
102         fa[1]=1;
103         dfs(1);
104         
105         //out11();
106         
107         int judge=0;
108         
109         for(int i=2;i<=n;++i)
110             for(int j=1;j<=n;++j)
111                 if(a[i][j]!=a[fa[i]][j]+quan[i]&&a[i][j]!=a[fa[i]][j]-quan[i])
112                 {
113                     //printf("i=%d j=%d
",i,j);
114                     judge=1;
115                 }
116         
117         /*printf("
");
118         for(int i=1;i<=n;++i)
119           printf("%d ",fa[i]);
120         printf("
");*/
121         
122         if(judge)
123         {
124             printf("No
");
125             continue;
126         }
127         else
128           printf("Yes
");
129         
130     dd maxl=0;
131     int order;
132     for(int i=1;i<=n;++i)
133     {
134         dd sum=0;int ci=0;
135         for(int j=first[i];j!=-1;j=a1[j].next)
136         {sum+=a1[j].w;++ci;}
137         sum/=(dd)ci;
138         //printf("i=%d sum=%.4lf
",i,sum);
139         if(sum>maxl){maxl=sum;order=i;}
140     }
141         
142         /*printf("val=
");
143         for(int i=1;i<=n;++i)
144           printf("%.2lf ",val[i]);
145         printf("
");*/
146         
147         printf("%d
",order);
148     }
149     //while(1);
150     return 0;
151 }

考试自己yy的，9个点