题目描述
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
题解
我机房一位数据狂魔出的题目和数据，感觉非常不爽。
本题原题是codeforces上一次7题比赛中的D题，不过说是原题，还是加强了。首先：第一问是cf原问题，解法是根据所给dist求出最小生成树，判断是否符合题意即可。注意：30%的数据会爆int，要开long long，还有据说cf原题可以用Kruskal卡过，出题人也卡掉了。但个人感觉prim好像更好想。
第二问是出题人自己加的。只要在做最小生成树时顺便记录一下即可。但是出题人之所以叫“数据狂魔”，是因为用prim有2个点还是会T。以下是我80分的代码，勉强卡进3s。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1e18
using namespace std;
int T,n,tag;
ll sum[2502],dis[2502],map[2502][2502];
int ct[2502],from[2502],pd[2502];
int zz,head[2502],q[2502];
struct bian{int to,nx;ll v;} e[5002];
void init()
{
scanf("%d",&n); tag=0;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{scanf("%I64d",&map[i][j]);
if(i==j&&map[i][j]!=0) tag=-1;
if(i!=j&&map[i][j]==0) tag=-1;
if(i>j&&map[i][j]!=map[j][i]) tag=-1;
}
}
//------------------------------------------------------------------------------
void insert(int x,int y,ll z)
{
zz++; e[zz].to=y; e[zz].v=z; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].v=z; e[zz].nx=head[y]; head[y]=zz;
}
void prim()
{
int i;
for(i=0;i<=n;i++)
{dis[i]=inf; head[i]=0; ct[i]=0; sum[i]=0; from[i]=0; pd[i]=0;}
dis[1]=0;
int x,j;
for(i=1;i<=n;i++)
{x=0;
for(j=1;j<=n;j++)
{if(!pd[j]&&dis[j]<dis[x]) x=j;}
pd[x]=1;
if(from[x])
{sum[x]+=map[from[x]][x]; sum[from[x]]+=map[from[x]][x];
ct[x]++; ct[from[x]]++;
insert(from[x],x,map[from[x]][x]);
}
for(j=1;j<=n;j++)
{
if(!pd[j]&&dis[j]>map[x][j])
{dis[j]=map[x][j];
from[j]=x;
}
}
}
}
//------------------------------------------------------------------------------
bool bfs(int s)
{
int i,x,p,t=0,w=1;
q[0]=s; pd[s]=1;
while(t<w)
{x=q[t]; t++;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(pd[p]) continue;
dis[p]=dis[x]+e[i].v;
q[w]=p; w++; pd[p]=1;
}
}
for(i=1;i<=n;i++)
{if(dis[i]!=map[s][i]) return false;}
return true;
}
void check()
{
int i,j;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++) {dis[j]=0; pd[j]=0;}
if(!bfs(i)) {puts("No"); return ;}
}
puts("Yes");
int ans=1;
for(i=2;i<=n;i++)
{if((double)(sum[i]/ct[i])>(double)(sum[ans]/ct[ans]))
ans=i;
}
printf("%d\n",ans);
}
int main()
{
freopen("treas.in","r",stdin);
freopen("treas.out","w",stdout);
scanf("%d",&T);
while(T--)
{init();
if(tag==-1) {puts("No"); continue;}
prim(); check();
}
return 0;
}
所以，想拿这20分，要加上一个堆优化prim，因为prim和dijkstra相似。至于判断生成树是否合法，O(n^2)就可以了，倍增反而更累更慢。本弱也想不出什么其他的优化了……由于不想背STL的写法，所以我还是手写堆，毕竟noip没开O2优化，不过还是很羡慕随手敲堆的大神。
还有……最坑爹的是，出题人要求随后两个点一定要加快速读入……
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define inf 1e15
#define ll long long
using namespace std;
int T,n,tag;
ll dis[2502],map[2502][2502],sum[2502];
int pd[2502],from[2502],ct[2502];
int zz,head[2502],q[2502],size;
struct bian{int to,nx;ll v;} e[6002];
struct DUI{int w;ll d;} dui[6250002];
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
n=read(); tag=0;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=read();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{if(map[i][j]==0&&i!=j) {tag=-1; return ;}
if(i==j&&map[i][j]!=0) {tag=-1; return ;}
if(map[i][j]!=map[j][i]) {tag=-1; return ;}
}
}
void insert(int x,int y,ll z)
{
zz++; e[zz].v=z; e[zz].to=y; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].v=z; e[zz].to=x; e[zz].nx=head[y]; head[y]=zz;
}
//-----------------------------------------------------------------------------
void heapfy(int x)
{
int l,r,minx=x;
l=x<<1; r=l+1;
if(l<=size&&dui[l].d<dui[minx].d) minx=l;
if(r<=size&&dui[r].d<dui[minx].d) minx=r;
if(minx!=x)
{swap(dui[minx],dui[x]);
heapfy(minx);
}
}
void del()
{
dui[1].w=dui[size].w; dui[1].d=dui[size].d; size--;
if(size>0) heapfy(1);
}
void weih(int x)
{
if(x<=1) return;
int i=x/2;
if(dui[i].d>dui[x].d)
{swap(dui[i],dui[x]); weih(i);}
}
void prim()
{
int i,j,x;
for(i=1;i<=n;i++)
{dis[i]=inf; head[i]=0; pd[i]=0;
from[i]=0; sum[i]=0; ct[i]=0;
}
size=1; dui[1].w=1; dui[1].d=0; dis[1]=0;
while(size>0)
{x=dui[1].w; del();
if(pd[x]) continue;
//cout<<x<<endl;
pd[x]=1;
if(from[x])
{sum[from[x]]+=dis[x]; sum[x]+=dis[x];
ct[from[x]]++; ct[x]++;
insert(from[x],x,dis[x]);
}
for(i=1;i<=n;i++)
{if(!pd[i]&&dis[i]>map[x][i])
{dis[i]=map[x][i]; from[i]=x;
size++; dui[size].w=i; dui[size].d=dis[i]; weih(size);
}
}
}
}
void bfs(int x)
{
dis[x]=0;
q[0]=x;
int now,i,t=0,w=1;
while(t<w)
{now=q[t]; t++;
for(i=head[now];i;i=e[i].nx)
{if(dis[e[i].to]==inf)
{dis[e[i].to]=dis[now]+e[i].v;
q[w]=e[i].to; w++;
}
}
}
}
void check()
{
int i,j;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++) dis[j]=inf;
bfs(i);
for(j=1;j<=n;j++)
{if(dis[j]!=map[i][j])
{printf("No\n"); return ;}
}
}
printf("Yes\n");
int x=1;
for(i=2;i<=n;i++)
{if((double)sum[i]/ct[i]>(double)sum[x]/ct[x])
x=i;
}
printf("%d\n",x);
}
int main()
{
freopen("treas.in","r",stdin);
freopen("treas.out","w",stdout);
T=read();
while(T--)
{init();
if(tag==-1) {printf("No\n"); continue;}
if(n==1) {printf("Yes\n"); puts("1"); continue;}
prim(); check();
}
return 0;
}