「NOIP模拟赛」藏宝图
背景
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%小数据外任意1<=dist[i][j]<=10^9,T<=5
题解
对于每个点与其它所有点的距离，显然距离最小的点一定与它直接相连
所以按照矩阵构造出最小生成树，对最小生成树bfs得出距离矩阵，与给出的矩阵对比
第二问在建树的过程中得出每个点的度数和连出的边权和最后更新答案
注意特判n=1，dis[i][j]=0(i<>j)的情况
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define linf 9223372036854775807LL #define ll long long #define pa pair<ll,int> using namespace std; 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; } double mx; int ans,T,n,tot; int last[2505],from[2505],cnt[2505],q[2505]; ll d[2505][2505],dis[2505],sum[2505]; bool vis[2505]; struct edge{int to,next;ll v;}e[5005]; void insert(int u,int v,ll w) { e[++tot].to=v;e[tot].next=last[u];last[u]=tot;e[tot].v=w; e[++tot].to=u;e[tot].next=last[v];last[v]=tot;e[tot].v=w; } void prim() { priority_queue<pa,vector<pa>,greater<pa> >q; for(int i=1;i<=n;i++)dis[i]=linf; q.push(make_pair(0,1));dis[1]=0; while(!q.empty()) { int now=q.top().second;q.pop(); if(vis[now])continue;vis[now]=1; if(from[now]) { cnt[now]++;cnt[from[now]]++; sum[now]+=dis[now];sum[from[now]]+=dis[now]; insert(now,from[now],dis[now]); } for(int i=1;i<=n;i++) if(!vis[i]&&d[now][i]<dis[i]) { dis[i]=d[now][i]; from[i]=now; q.push(make_pair(dis[i],i)); } } } void bfs(int x) { for(int i=1;i<=n;i++)dis[i]=linf; int head=0,tail=1; q[0]=x;dis[x]=0; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(dis[e[i].to]==linf) { dis[e[i].to]=dis[now]+e[i].v; q[tail++]=e[i].to; } } } bool jud() { for(int i=1;i<=n;i++) { bfs(i); for(int x=1;x<=n;x++) if(dis[x]!=d[i][x])return 0; else if(x!=i&&d[i][x]==0)return 0; } return 1; } int main() { T=read(); while(T--) { memset(last,0,sizeof(last)); memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); memset(dis,0,sizeof(dis)); memset(sum,0,sizeof(sum)); ans=mx=tot=0; n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=read(); prim(); if(!jud()){puts("No");continue;} puts("Yes"); if(n==1){puts("1");continue;} for(int i=1;i<=n;i++) { if(double(sum[i])/cnt[i]>=mx) ans=i,mx=(double)(sum[i])/cnt[i]; } printf("%d\n",ans); } return 0; } |
Subscribe
计数器 9787147
OI 课件=>
OI 课件=>