题目描述 Czy爬上黑红树，到达了一个奇怪的地方…… Czy发现了一张奇怪的藏宝图。
图上有n个点，m条无向边。
已经标出了图中两两之间距离dist。
但是czy知道，只有当图刚好又是一颗树的时候，这张藏宝图才是真的。
如果藏宝图是真的，那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。
请计算这是不是真的藏宝图，如果是真的藏宝之处在哪里。
输入 输入数据第一行一个数T,表示T组数据。
对于每组数据，第一行一个n，表示藏宝图上的点的个数。
接下来n行,每行n个数，表示两两节点之间的距离。
输出 输出一行或两行。
第一行”Yes”或”No”，表示这是不是真的藏宝图。
若是真的藏宝图，第二行再输出一个数，表示哪个点是藏宝之处。
样例输入
2
3
0 7 9
7 0 2
9 2 0
3
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： 这个题真心恶心，考试的时候用spfa跑了40，而且没有用long long，有间接连边且距离和为两点距离则说明在一棵树上，暴力的40........ 正解： 先不管是否为一棵树，跑MST，并且在MST中dfs暴搜一遍，找到MST上的dis2并记录一下经过每一个点的路径长度，如果dis[i][j]==dis2[i][j]则说明是一棵树，否则不是。
还有记得开long long，所有的，否则有几个点过不了 原来这么简单。
。
。
还是太弱啊，接下来几天考试要加油了！
！
！
！
！
1 贴代码（略丑）：
2
3 #include
4 #include
5 #include
6 #include
7 #include
8 #define int long long
9 using namespace std;
10 __attribute__((optimize("O3")))long long read() {
11 long long s=0,f=1;
12 char ch=getchar();
13 while(ch>'9'||ch<'0') {
14 if(ch=='-')
15 f=-1;
16 ch=getchar();
17 }
18 while(ch>='0'&&ch<='9') {
19 s=(s<<1)+(s<<3)+(ch^48);
20 ch=getchar();
21 }
22 return s*f;
23 }
24 int n,T,tot,r[2505];
25 long long dis2[2501][2501],dis[2501][2501];
26 struct oo {
27 int to,next,vv;
28 } c[10005];
29 __attribute__((optimize("O3")))void add(int x,int y,int z) {
30 c[tot].to=y;
31 c[tot].vv=z;
32 c[tot].next=r[x];
33 r[x]=tot++;
34 }
35 long long lowcost[2505],mst[2501];
36 long double num[2505],indexx[2505];
37 bool u[2505];
38 __attribute__((optimize("O3")))void clean() {
39 tot=0;
40 memset(dis,0,sizeof(dis));
41 memset(dis2,0,sizeof(dis2));
42 memset(r,-1,sizeof(r));
43 memset(lowcost,0x7f,sizeof(lowcost));
44 memset(mst,0,sizeof(mst));
45 memset(u,1,sizeof(u));
46 memset(indexx,0,sizeof(indexx));
47 memset(num,0,sizeof(num));
48 }
49 __attribute__((optimize("O3")))void prim() {
50 lowcost[1]=0;
51 for(int i=1;i<=n;i++){
52 int k=0;
53 for(int j=1;j<=n;j++){
54 if(u[j]&&lowcost[j]0) {
120 pd=0;
121 break;
122 }
123 }
124 if(!pd) {
125 break;
126 }
127 }
128 /*for(int i=1;i<=n;i++){
129 for(int j=1;j<=n;j++){
130 cout<oo) {
142 ji=i;
143 oo=num[i];
144 }
145 }
146 printf("Yes\n%d\n",ji);
147 }
148 }
149 return 0;
150 }
转载于:https://www.cnblogs.com/forevergoodboy/p/7252726.html