藏宝图 treas"/>
藏宝图 treas
【题目描述】：
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。【时间限制、数据范围及描述】：
时间：2s 空间：256M
对于30%数据，n<=50,1<=树上的边的长度<=10^9；
对于50%数据，n<=600；
对于100%数据，1<=n<=2500；
除30%小数据外任意0<=dist[i][j]<=10^9,T<=5。
【题解Here!】
最小生成树与最短路的混合体。。。
把图转成树，在跑 spfa ,得到的最短路径与原矩阵比较。
注：我用的最小生成树是 kruskal ,记得改成 prim（因为我只会 kruskal ，吃枣药丸(逃)）。。。
附代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#define MAXN 2510
using namespace std;
int n,s,c,d,head[MAXN],fa[MAXN];
unsigned long long path[MAXN],map[MAXN][MAXN];
bool vis[MAXN];
struct node1{int next,to;long long w;
}a[MAXN*MAXN<<1];
struct node2{int u,v;long long w;
}b[MAXN*MAXN];
struct node3{int s1;long long s2;
}g[MAXN];
inline long long read(){long long date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w;
}
bool cmp(const node2 &x,const node2 &y){return x.w<y.w;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void uniun(int x,int y){x=find(x);y=find(y);if(x!=y)fa[y]=x;}
inline int relax(int u,int v,long long w){if(path[v]>path[u]+w){path[v]=path[u]+w;return 1;}return 0;
}
void aadd(int u,int v,long long w){a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;
}
void badd(int u,int v,long long w){b[d].u=u;b[d].v=v;b[d].w=w;d++;
}
void kruskal(){int s=0;for(int i=1;i<d&&s<n-1;i++)if(find(b[i].u)!=find(b[i].v)){uniun(b[i].u,b[i].v);aadd(b[i].u,b[i].v,b[i].w);s++;}
}
void spfa(){int u,v;queue<int> q;for(int i=1;i<=n;i++){path[i]=INT_MAX<<2;vis[i]=false;}path[s]=0;vis[s]=true;q.push(s);while(!q.empty()){u=q.front();q.pop();vis[u]=false;for(int i=head[u];i;i=a[i].next){v=a[i].to;if(relax(u,v,a[i].w)&&!vis[v]){vis[v]=true;q.push(v);}}}
}
void init(){c=d=1;memset(head,0,sizeof(head));memset(g,0,sizeof(g));n=read();for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){map[i][j]=read();if(j<i)badd(i,j,map[i][j]);}sort(b+1,b+d,cmp);kruskal();
}
void work(){int v,ans;double maxn=0;bool flag=true;for(s=1;s<=n;s++){spfa();for(int i=1;i<=n&&flag;i++)if(map[s][i]!=path[i])flag=false;if(!flag){printf("No\n");return;}}printf("Yes\n");for(int i=1;i<=c;i++){v=a[i].to;g[v].s1++;g[v].s2+=a[i].w;}for(int i=1;i<=n;i++){double x=g[i].s2*1.000000/g[i].s1;if(x>maxn){maxn=x;ans=i;}}printf("%d\n",ans);
}
int main(){int t;t=read();while(t--){init();if(n==1){printf("Yes\n1\n");continue;}work();}return 0;
}更多推荐
藏宝图 treas
发布评论