[POI 2018] Plan Metra

[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=5100

[算法]

首先分两类考虑 :

1. 1 -> N的路径不经过其它节点 ， 我们只需判断(d1i - d2i)的绝对值是否全部相等

2. 1 -> N的路径经过了其它节点 ， 那么显然 , 1 -> N这条链的长度为min{ d1i + d2i } , 所有d1i + d2i等于链长的节点都在链上 ， 将其余节点的d1i和d2i作差 ， 即可O(1)判断出这个节点是挂在链上的哪个节点的

时间复杂度 : O(N)

[代码]

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int N = 1e6 + ;

const int inf = 2e9;

const int V = 1e7 + ;

struct edge {

    int to , w , nxt;

} e[N << ];

int n , m , tot;

int head[N] , d1[N] , d2[N] , mp[V];

template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); }

template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); }

template <typename T> inline void read(T &x) {

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline void addedge(int u , int v , int w)

{

    ++tot;

    e[tot] = (edge){v , w , head[u]};

    head[u] = tot;

}

inline void add(int x , int y , int w) {

    addedge(x , y , w);

    addedge(y , x , w);

}

inline void dfs(int u , int par) {

    for (int i = head[u]; i; i = e[i].nxt) {

        int v = e[i].to , w = e[i].w;

        if (v != par) {

            printf("%d %d %d\n" , u , v , w);

            dfs(v , u);

        }

    }

}

inline bool check()

{

    int val = abs(d1[] - d2[]);

    if (val == ) return false;

    for (int i = ; i < n; ++i)

        if (abs(d1[i] - d2[i]) != val) return false;

    printf("TAK\n");

    printf("%d %d %d\n" ,  , n , val);

    for (int i = ; i < n; ++i)

        if (d1[i] >= d2[i]) printf("%d %d %d\n" , n , i , d2[i]);

        else printf("%d %d %d\n" ,  , i , d1[i]);

    return true;

}

int main() {

    read(n);

    if (n == )

    {

        printf("TAK\n");

        printf("%d %d %d\n" ,  ,  , );

        return ;

    }

    for (int i = ; i < n; ++i) read(d1[i]);

    for (int i = ; i < n; ++i) read(d2[i]);

    if (check())

        return ;

    int line = inf;

    for (int i = ; i < n; ++i) chkmin(line , d1[i] + d2[i]);

    mp[] = ;

    mp[line] = n;

    for (int i = ; i < n; ++i) {

            if (d1[i] + d2[i] == line) {

                    if (mp[d1[i]] != ) {

                            printf("NIE\n");

                            return ;

                    }

                    mp[d1[i]] = i;

            }

    }

    int pre = ;

    for (int i = ; i <= line; ++i) {

            if (mp[i]) {

                    add(mp[pre] , mp[i] , i - pre);

                    pre = i;

            }

    }

    for (int i = ; i < n; ++i) {

            if (d1[i] + d2[i] - line != ) {

                    int tmp = d1[i] + d2[i] - line;

                    if (tmp & ) {

                            printf("NIE\n");

                            return ;

                    }

                    int len = d1[i] - tmp / ;

                    if (len <  || mp[len] == ) {

                            printf("NIE\n");

                            return ;

                    }

                    add(i , mp[len] , tmp / );

            }

    }

    puts("TAK");

    dfs( , );

    return ;

}