当前位置：首页 > news >正文

打卡信奥刷题（2967）用C++实现信奥题 P5959 [POI 2018] Plan metra

news 2026/8/27 19:15:29

P5959 [POI 2018] Plan metra

题目描述

有一棵nnn个点的无根树，每条边有一个正整数权值，表示长度，定义两点距离为在树上的最短路径的长度。

已知222到 $ n-1$ 每个点在树上与111和nnn的距离，请根据这些信息还原出这棵树。

输入格式

第一行包含一个正整数nnn，表示点数。

第二行包含n−2n-2n−2个正整数d(1,2),d(1,3),...,d(1,n−1)d(1,2),d(1,3),...,d(1,n-1)d(1,2),d(1,3),...,d(1,n−1)，分别表示每个点到111的距离。

第三行包含n−2n-2n−2个正整数d(n,2),d(n,3),...,d(n,n−1)d(n,2),d(n,3),...,d(n,n-1)d(n,2),d(n,3),...,d(n,n−1)，分别表示每个点到nnn的距离。

输出格式

若无解，输出NIE。

否则第一行输出TAK，接下来n−1n-1n−1行每行三个正整数u,v,cu,v,cu,v,c，表示存在一条长度为ccc的连接uuu和vvv两点的树边。

若有多组解，输出任意一组即可。

本题使用 Special Judge。

输入输出样例 #1

输入 #1

7 6 6 2 2 1 5 3 5 1 4

输出 #1

TAK 1 5 2 5 7 1 5 2 4 7 3 3 1 4 2 1 6 1

说明/提示

对于100%100\%100%的数据，2≤n≤5000002\le n\le 5000002≤n≤500000，1≤d≤10000001\le d\le 10000001≤d≤1000000，1≤u,v≤n1\le u,v\le n1≤u,v≤n，1≤c≤10000001\le c\le10000001≤c≤1000000。

C++实现

#include<cstring>#include<iostream>#include<algorithm>#include<cstdlib>#include<cmath>usingnamespacestd;intn;voidWA(){puts("NIE"),exit(0);}structdata{intx,y,id;}f[500005];boolcmp(data a,data b){returna.x+a.y==b.x+b.y?a.x<b.x:a.x+a.y<b.x+b.y;}boolCMP(data a,data b){returna.x<b.x;}intope[10000005],*val=ope+5000000;//桶intfa[500005],v[500005];signedmain(){intM=0x3f3f3f3f;scanf("%d",&n);//cout<<n<<endl;for(inti=1;i<=n;i++)f[i].id=i;for(inti=2;i<n;i++)scanf("%d",&f[i].x);for(inti=2;i<n;i++)scanf("%d",&f[i].y);for(inti=2;i<n;i++)M=min(M,f[i].x+f[i].y);f[1]={0,M,1},f[n]={M,0,n};sort(f+1,f+n+1,cmp);//排序来分隔在线上的和不在的。ints;val[-M]=1;//往桶里塞进d(1,1)-d(1,n)for(s=2;s<=n;s++){if(f[s].x+f[s].y==M){//在线上if(f[s].x==f[s-1].x)WA();//点间距离!=0val[f[s].x-f[s].y]=s;}elsebreak;//不在}for(inti=s;i<=n;i++){int&t=val[f[i].x-f[i].y];if(t)fa[i]=t,v[i]=f[i].x-f[t].x;elseWA();}puts("TAK");for(inti=2;i<s;i++)printf("%d %d %d\n",f[i-1].id,f[i].id,f[i].x-f[i-1].x);for(inti=s;i<=n;i++)printf("%d %d %d\n",f[fa[i]].id,f[i].id,v[i]);return0;}