http://www.lydsy.com/JudgeOnline/problem.php?id=5100
1、找到d1[i]+dn[i] 最小的点，作为1到n链上的点
2、令链长为D，若abs（d1[i]-dn[i]）==D，则 i 与1或n 连边
3、对于链上除去1和n的点k，若 dn[i]-d1[i]==dn[k]-d1[k]，则i与k连边
若1到n的链上没有点，即1与n直接相连，那么所有的d1[i]-dn[i] 相等 且 不为 0
特判n=2，输出1 2 任意长度[1,1e6]
无解的情况：
1、找出的链上的点，存在两个点i，j，d1[i]==d1[j]
2、对于某个点i，找不到对应的点k
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 500001
#define M 1000001 int dis1[N],disn[N];
int cnt[M<<]; int chain[N]; bool vis[N]; struct node1
{
int id,d,bl;
}e[N];
struct node2
{
int id,d;
}g[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(int p,int q)
{
return dis1[p]<dis1[q];
} bool cmp2(node1 p,node1 q)
{
return p.d<q.d;
} bool cmp3(node2 p,node2 q)
{
return p.d<q.d;
} int main()
{
//freopen("test.in","r",stdin);
//freopen("my.out","w",stdout);
int n;
read(n);
if(n==)
{
printf("TAK\n1 2 1");
return ;
}
for(int i=;i<n;++i) read(dis1[i]);
for(int i=;i<n;++i) read(disn[i]);
int sta=abs(dis1[]-disn[]);
bool tag=true;
for(int i=;i<n && tag;++i)
if(abs(dis1[i]-disn[i])!=sta) tag=false;
if(tag && sta)
{
puts("TAK");
printf("1 %d %d\n",n,sta);
for(int i=;i<n;++i)
if(dis1[i]>disn[i]) printf("%d %d %d\n",n,i,dis1[i]-sta);
else printf("1 %d %d\n",i,disn[i]-sta);
return ;
}
int mid=;
dis1[]=1e7;
for(int i=;i<n;++i)
if(dis1[i]+disn[i]<dis1[mid]+disn[mid]) mid=i;
int D=dis1[mid]+disn[mid];
int m=;
for(int i=;i<n;++i)
if(dis1[i]+disn[i]==D) chain[++m]=i,vis[i]=true;
sort(chain+,chain+m+,cmp);
for(int i=;i<m;++i)
if(dis1[chain[i]]==dis1[chain[i+]])
{
printf("NIE");
return ;
}
for(int i=;i<=m;++i)
{
g[i].id=chain[i];
g[i].d=disn[chain[i]]-dis1[chain[i]];
}
sort(g+,g+m+,cmp3);
int tot=;
for(int i=;i<n;++i)
if(!vis[i])
{
e[++tot].id=i;
e[tot].d=disn[i]-dis1[i];
}
sort(e+,e+tot+,cmp2);
int now=;
for(int i=;i<=tot;++i)
{
if(abs(dis1[e[i].id]-disn[e[i].id])==D) continue;
if(now>m)
{
puts("NIE");
return ;
}
if(e[i].d<g[now].d)
{
puts("NIE");
return ;
}
else if(e[i].d==g[now].d) e[i].bl=g[now].id;
else
{
while(now<=m && e[i].d>g[now].d) now++;
i--;
}
}
// return 0;
puts("TAK");
printf("1 %d %d\n",chain[],dis1[chain[]]);
for(int i=;i<=m;++i) printf("%d %d %d\n",chain[i-],chain[i],dis1[chain[i]]-dis1[chain[i-]]);
printf("%d %d %d\n",chain[m],n,disn[chain[m]]);
for(int i=;i<n;++i)
if(dis1[i]-disn[i]==D)
{
vis[i]=true;
printf("%d %d %d\n",n,i,disn[i]);
}
else if(disn[i]-dis1[i]==D)
{
vis[i]=true;
printf("1 %d %d\n",i,dis1[i]);
}
for(int i=;i<=tot;++i)
if(!vis[e[i].id]) printf("%d %d %d\n",e[i].bl,e[i].id,dis1[e[i].id]-dis1[e[i].bl]);
return ;
}
5100: [POI2018]Plan metra
Time Limit: 40 Sec Memory Limit: 128 MBSec Special Judge
Submit: 277 Solved: 69
[Submit][Status][Discuss]
Description
有一棵n个点的无根树，每条边有一个正整数权值，表示长度，定义两点距离为在树上的最短路径的长度。
已知2到n-1每个点在树上与1和n的距离，请根据这些信息还原出这棵树。
Input
第一行包含一个正整数n(2<=n<=500000)，表示点数。
第二行包含n-2个正整数d(1,2),d(1,3),...,d(1,n-1)，分别表示每个点到1的距离。
第三行包含n-2个正整数d(n,2),d(n,3),...,d(n,n-1)，分别表示每个点到n的距离。
输入数据保证1<=d<=1000000。
Output
若无解，输出NIE。
否则第一行输出TAK，接下来n-1行每行三个正整数u,v,c(1<=u,v<=n,1<=c<=1000000)
表示存在一条长度为c的连接u和v两点的树边。
若有多组解，输出任意一组。
Sample Input
7
6 6 2 2 1
5 3 5 1 4
6 6 2 2 1
5 3 5 1 4
Sample Output
TAK
1 5 2
5 7 1
5 2 4
7 3 3
1 4 2
1 6 1
1 5 2
5 7 1
5 2 4
7 3 3
1 4 2
1 6 1