题目描述

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

 

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

 

输入

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

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

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

输出

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

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

样例输入

230 7 97 0 29 2 030 2 72 0 97 9 0

样例输出

Yes1Yes3样例解释:第一棵树的形状是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<
            
             <<" ";131 }132 cout<
             
              oo) {142 ji=i;143 oo=num[i];144 }145 }146 printf("Yes\n%d\n",ji);147 }148 }149 return 0;150 }