HDU 4274 Spy's Work (树 DFS)

给定N个点，每个点都有一个唯一的前驱结点（点1为大boss），每个点的实际权值是子节点的求和值。现在给出某些点的权值的估算（> , = , < ），问这些估算是否会有冲突，现在保证每个点的权值是大于等于1的。

分析：判断标准为每个点的上下界，初始化为INF和1，每个点上下界可以根据给出的信息，或者搜索出的信息进行更新，如果出现上界小于下界的情况就说明矛盾了。

计算过程中数据量竟然没有超过int................

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

# define INF 0x7FFFFFFF

using namespace std;

int n,m,flag;

struct Guess {

    int high,low;

    char c;

} guess[10001];

struct node {

    int s,e,next;

} ed[10001];

int head[10001],num;

void init() {

    memset(head,-1,sizeof(head));

    num = 0;

    flag = 1;

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

        guess[i].low = 1;

        guess[i].high = INF;

    }

}

void add(int s,int e) {

    ed[num].s = s;

    ed[num].e = e;

    ed[num].next = head[s];

    head[s] = num++;

}

void cmp(int i,int h,int l) {

    int hh = min(guess[i].high ,h);

    int ll = max(guess[i].low,l);

    if(hh < ll) flag = 0;

    guess[i].high = hh;

    guess[i].low = ll;

}

void dfs(int v0) {

    if(flag == 0) return ;

    int h = INF,l = 1;

    for(int i=head[v0]; i != -1; i= ed[i].next) {

        int e = ed[i].e;

        dfs(e);

        l += guess[e].low;

    }

    cmp(v0,h,l);

}

int main() {

    int t,a,b;

    char c;

    while(scanf("%d",&n) != EOF) {

        init();

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

            scanf("%d",&t);

            add(t,i);

        }

        scanf("%d",&m);

        int h,l;

        for(int i=0; i<m; i++) {

            scanf("%d %c %d",&a,&c,&b);

            h = INF;

            l = 1;

            if(c == '=') {

                l = b; h = b;

            }

            if(c == '<') h = b - 1;

            if(c == '>') l = b + 1;

            cmp(a,h,l);

        }

        dfs(1);

        if(flag) printf("True\n");

        else printf("Lie\n");

    }

    return 0;

}

巴特西

HDU 4274 Spy's Work (树 DFS)

最新文章

热门文章