【最小生成树】藏宝图(prim)

题目描述

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

输入

输入数据第一行一个数T,表示T组数据。
对于每组数据，第一行一个n，表示藏宝图上的点的个数。
接下来n行,每行n个数，表示两两节点之间的距离。

输出

输出一行或两行。第一行”Yes”或”No”，表示这是不是真的藏宝图。
若是真的藏宝图，第二行再输出一个数，表示哪个点是藏宝之处。

样例输入

样例输出

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

  1 #include <iostream>
  2 #include <bits/stdc++.h>
  3 using namespace std;
  4 const int N = 2505;
  5 typedef long long ll;
  6 ll mapp[N][N],nmp[N][N];
  7 ll d[N],from[N];
  8 bool vis[N];
  9 struct Edge
 10 {
 11     int u;
 12     int v;
 13     ll w;
 14     int net;
 15 } edge[N*2];
 16 int cnt_edge=0;
 17 int head[N*2];
 18 void add_edge(int fr,int to,ll w)
 19 {
 20     edge[cnt_edge].v=to;
 21     edge[cnt_edge].w=w;
 22     edge[cnt_edge].net=head[fr];
 23     head[fr]=cnt_edge++;
 24 }
 25 void init()
 26 {
 27     memset(head,-1,sizeof(head));
 28     memset(nmp,0,sizeof(nmp));
 29     memset(d,0x7f7f,sizeof(d));
 30     memset(vis,0,sizeof(vis));
 31     memset(from,0,sizeof(from));
 32     memset(edge,0,sizeof(edge));
 33     cnt_edge=0;
 34 }
 35 int n;
 36 void prim()
 37 {
 38     d[1]=0;
 39     for(register int i=1; i<=n; i++)
 40     {
 41         int x=0;
 42         for(register int j=1; j<=n; j++)
 43         {
 44             if(!vis[j]&&(x==0||d[j]<d[x]))
 45                 x=j;
 46         }
 47         vis[x]=1;
 48         for(register int y=1; y<=n; y++)
 49         {
 50             if(!vis[y]&&mapp[x][y]<d[y])
 51             {
 52                 from[y]=x;
 53                 d[y]=mapp[x][y];
 54             }
 55 
 56         }
 57     }
 58 
 59 }
 60 void dfs(int fa,int fr,int now)
 61 {
 62     for(register int i=head[fr];i!=-1;i=edge[i].net)
 63     {
 64         int temp=edge[i].v;
 65         if(fa==temp)
 66             continue;
 67         nmp[now][temp]=nmp[now][fr]+edge[i].w;
 68         dfs(fr,temp,now);
 69     }
 70 }
 71 
 72 int main()
 73 {
 74     int T;
 75     cin>>T;
 76     while(T--)
 77     {
 78         cin>>n;
 79         bool flag=true;
 80         for(register int i=1; i<=n; i++)
 81         {
 82             for(register int j=1; j<=n; j++)
 83             {
 84                 ll x;
 85                 scanf("%lld",&x);
 86                 mapp[i][j]=x;
 87                 if(i==j&&x!=0)
 88                 {
 89                     flag=false;
 90                 }
 91             }
 92         }
 93         for(register int i=1; i<=n; i++)
 94         {
 95             for(register int j=1; j<=i; j++)
 96             {
 97                 if(mapp[i][j]!=mapp[j][i])
 98                 {
 99                     flag=false;
100                     break;
101                 }
102             }
103         }
104         if(flag)
105         {
106             init();
107             prim();
108             for(register int i=2;i<=n;i++)
109             {
110                 add_edge(i,from[i],d[i]);
111                 add_edge(from[i],i,d[i]);
112             }
113             for(register int i=1;i<=n;i++)
114             {
115                 dfs(-1,i,i);
116             }
117             for(register int i=1;i<=n;i++)
118             {
119                 for(register int j=1;j<=n;j++)
120                 {
121                     if(mapp[i][j]!=nmp[i][j])
122                     {
123                         flag=false;
124                     }
125                 }
126             }
127         }
128         if(flag)
129         {
130             double maxx=-1;
131             int num;
132             double tot=0;
133             for(register int i=1;i<=n;i++)
134             {
135                 double sum=0;
136                 tot=0;
137                 for(register int j=head[i];j!=-1;j=edge[j].net)
138                 {
139                     sum+=edge[j].w;
140                     tot++;
141                 }
142                 if(tot)
143                 {
144                     sum/=(tot*1.0);
145                 }
146                 if(sum>maxx)
147                 {
148                     maxx=sum;
149                     num=i;
150                 }
151             }
152             printf("Yes
");
153             cout << num << endl;
154         }
155         else
156             cout << "No" << endl;
157     }
158 
159     //cout << "Hello world!" << endl;
160     return 0;
161 }

View Code