acdream 1042: Classification of the species 抽象无根树并查集

首先贴上 NBU 嘟嘟洒水车 大神的解题思路:

http://www.acdream.net/problem.php?id=1042


题目大意：
(把物种和分类都看成节点。)

有一颗未知树，一人每次询问两个叶子节点，另一个人回答其lca，判回答之间是否有矛盾。


解法：
将每条陈述按照lca的深度由深到浅排序，然后扫一遍开始并查集。

比如说现在搞到这条陈述：x y a，那么查到xy的根节点 x_father y_father。由于是按照a的深度由深到浅搞的，所以a必然是x_father和y_father的祖先。那就分类讨论这样是否可能：

一、a是x(y)_father之一：

1、x_father和y_father都是a：ok；

2、仅x_father等于a：那么depth(y_father)必须大于depth(a)，反之亦然。

二、a不是x(y)_father之一：

1、x_father和y_father相同：!ok；(x_father=y_father说明xy的lca至浅是x_father，而depth(a)<=depth(x_father)&&a!=x_father => depth(a)<depth(x_father)，所以xy的lca不应该是a)

2、x_father和y_father不同：那只要depth(a)<depth(x_father)&&depth(a)<depth(y_father)就好了。
讨论完后如果正确，那就并查集那样并起来，继续搞。


中间有矛盾就是wrong，没矛盾的话，根据并的过程就能给出一个可行解，maybe right了。

按照这个思路写出来后提交死命 WA, 百思不得其解..

后找到 BSBandme 大神,求得代码. 再次感谢..好人啊....

发现写法是一样的. 又一条条语句分析...苍天啊.大地啊..竟然是我的 if条件语句中, 运算符优先级问题出错了. 没打括号..修改后果断AC.

解题代码: 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int inf = 0x3fffffff;
const int N = 300111;
int n, m, s, st[N], dep[N];

struct node{
    int x, y, a, d;
    void read(){
        scanf("%d%d%d",&x,&y,&a);    
        d = dep[a];    
    }
    bool operator < (node tmp) const{
        return d > tmp.d;    
    }
}word[N];

int find( int x )
{    
    return ( x == st[x] )? x : ( st[x] = find( st[x] ) );
}
int main(){
    while( scanf("%d%d%d", &n,&m,&s) != EOF)
    {
        for(int i = 1; i <= m; i++)
            scanf("%d", dep+i);
        for(int i = m+1; i <= m+n; i++)
            dep[i] = inf;
        for(int i = 0; i < s; i++)
            word[i].read();
        sort( word, word+s );
        for(int i = 1; i <= m+n; i++)
            st[i] = i;
        bool flag = true;    
        for(int i = 0; i < s && flag; i++)
        {
            int a = word[i].a;
            int x = word[i].x + m, y = word[i].y + m;
            int xf = find( x ), yf = find( y );    
            if( (xf == a) || (yf == a) )
            {
                if( (xf == a) && (yf == a) ) continue;
                else
                {
                    if( (xf == a) && (dep[yf] > dep[a]) )
                        st[yf] = a;    
                    else if( (yf == a) && (dep[xf] > dep[a]) )
                        st[xf] = a;    
                    else    flag = false;    
                }
            }
            else
            {
                if( (xf != yf) && (dep[xf] > dep[a]) && (dep[yf] > dep[a]) )
                    st[xf] = st[yf] = a; 
                else    flag = false;
            }    
/*    //另一种写法
            if( xf != a ){
                if( dep[xf] == dep[a] )
                {    flag = false; break; }
                st[xf] = a;    
            } 
            if( yf != a ){
                if( dep[yf] == dep[a] )
                {    flag = false; break; }
                st[yf] = a;    
            }    
            if( xf == yf && xf != a )
            {    flag = false; break; }
        */    
        }
        puts( flag == true ? "maybe right" : "wrong" );    
    }
    return 0;    
}