bzoj千题计划249：bzoj5100: [POI2018]Plan metra

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<<1];

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=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; 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==2) 
    {
        printf("TAK
1 2 1");
        return 0;
    }
    for(int i=2;i<n;++i) read(dis1[i]);
    for(int i=2;i<n;++i) read(disn[i]);
    int sta=abs(dis1[2]-disn[2]);
    bool tag=true;
    for(int i=3;i<n && tag;++i)
        if(abs(dis1[i]-disn[i])!=sta) tag=false;
    if(tag && sta)
    {
        puts("TAK");
        printf("1 %d %d
",n,sta);
        for(int i=2;i<n;++i)
            if(dis1[i]>disn[i]) printf("%d %d %d
",n,i,dis1[i]-sta);
            else printf("1 %d %d
",i,disn[i]-sta);
        return 0;
    }
    int mid=0;
    dis1[0]=1e7;
    for(int i=2;i<n;++i)
        if(dis1[i]+disn[i]<dis1[mid]+disn[mid]) mid=i;
    int D=dis1[mid]+disn[mid];
    int m=0;
    for(int i=2;i<n;++i)
        if(dis1[i]+disn[i]==D) chain[++m]=i,vis[i]=true;
    sort(chain+1,chain+m+1,cmp);
    for(int i=1;i<m;++i)
        if(dis1[chain[i]]==dis1[chain[i+1]]) 
        {
           printf("NIE");
           return 0;
        }
    for(int i=1;i<=m;++i)
    {
        g[i].id=chain[i];
        g[i].d=disn[chain[i]]-dis1[chain[i]];
    }
    sort(g+1,g+m+1,cmp3);
    int tot=0;
    for(int i=2;i<n;++i)
        if(!vis[i])
        {
            e[++tot].id=i;
            e[tot].d=disn[i]-dis1[i];
        }
    sort(e+1,e+tot+1,cmp2);
    int now=1;
    for(int i=1;i<=tot;++i)
    {
        if(abs(dis1[e[i].id]-disn[e[i].id])==D) continue;
        if(now>m)
        {
            puts("NIE");
            return 0;
        }
        if(e[i].d<g[now].d) 
        {
            puts("NIE");
            return 0;
        }
        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
",chain[1],dis1[chain[1]]);
    for(int i=2;i<=m;++i) printf("%d %d %d
",chain[i-1],chain[i],dis1[chain[i]]-dis1[chain[i-1]]);
    printf("%d %d %d
",chain[m],n,disn[chain[m]]);
    for(int i=2;i<n;++i)
        if(dis1[i]-disn[i]==D) 
        {
            vis[i]=true;
            printf("%d %d %d
",n,i,disn[i]);
        }
        else if(disn[i]-dis1[i]==D)
        {
            vis[i]=true;
            printf("1 %d %d
",i,dis1[i]);
        }
    for(int i=1;i<=tot;++i)
        if(!vis[e[i].id]) printf("%d %d %d
",e[i].bl,e[i].id,dis1[e[i].id]-dis1[e[i].bl]);
    return 0;
}

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

Sample Output

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