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输入 #17 6 6 2 2 1 5 3 5 1 4输出 #1TAK 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≤5000001≤d≤10000001\le d\le 10000001≤d≤10000001≤u,v≤n1\le u,v\le n1≤u,v≤n1≤c≤10000001\le c\le10000001≤c≤1000000。C实现#includecstring#includeiostream#includealgorithm#includecstdlib#includecmathusingnamespacestd;intn;voidWA(){puts(NIE),exit(0);}structdata{intx,y,id;}f[500005];boolcmp(data a,data b){returna.xa.yb.xb.y?a.xb.x:a.xa.yb.xb.y;}boolCMP(data a,data b){returna.xb.x;}intope[10000005],*valope5000000;//桶intfa[500005],v[500005];signedmain(){intM0x3f3f3f3f;scanf(%d,n);//coutnendl;for(inti1;in;i)f[i].idi;for(inti2;in;i)scanf(%d,f[i].x);for(inti2;in;i)scanf(%d,f[i].y);for(inti2;in;i)Mmin(M,f[i].xf[i].y);f[1]{0,M,1},f[n]{M,0,n};sort(f1,fn1,cmp);//排序来分隔在线上的和不在的。ints;val[-M]1;//往桶里塞进d(1,1)-d(1,n)for(s2;sn;s){if(f[s].xf[s].yM){//在线上if(f[s].xf[s-1].x)WA();//点间距离!0val[f[s].x-f[s].y]s;}elsebreak;//不在}for(intis;in;i){inttval[f[i].x-f[i].y];if(t)fa[i]t,v[i]f[i].x-f[t].x;elseWA();}puts(TAK);for(inti2;is;i)printf(%d %d %d\n,f[i-1].id,f[i].id,f[i].x-f[i-1].x);for(intis;in;i)printf(%d %d %d\n,f[fa[i]].id,f[i].id,v[i]);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容