QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks
    这几天做了些并查集的题目,其中有一些简单题就是直接套模板,没什么可以思考的。但今天做的两道题就稍微有些难度了,只有真正理解了“并”和“查”的过程才有解题的思路。

思路:
    告诉你[a,b]之间1个数的奇偶情况,那么你就可以在a-1和b之间连一条边,权值就是其奇偶情况。这样一来,比如[1,2]和[3,4]的情况已知,[1,4]的情况也就知道了。当题目给出[a,b]的情况时,首先分别从a和b往上找,找到他们的根r1和r2,如果r1 !=  r2,表示a,b之间的奇偶情况还不确定,就将r1和r2之间连起来,根据a到r1的权值、b到r2的权值和题目所给的奇偶情况,设置r1和r2之间的权值,以符合题目要求。若r1 == r2,则表示[a,b]之间情况已确定,根据a到r1的权值和b到r2的权值,就可以判断题目所给的[a,b]的情况是否为真。
    其实当时做的时候,还不是很懂,但没想到稀里糊涂的就AC了。推荐一下这个网页:http://hi.baidu.com/fandywang_jlu/blog/item/b49e40893ddbb0b00f244485.html,这里面介绍并查集挺详细的,还有不少推荐题目,有些还不会做。:P

代码:

#include <iostream>
#include <map>
using namespace std;

const int MAX = 10005;

int n, p;
int pre[MAX];
int parity[MAX];        //i到目前集合的根的奇偶情况
map<int, int> numIndex;        //用于离散化

int Find (int x)
{
    if ( pre[x] == -1 )
        return x;
    int f;
    f = Find(pre[x]);
    parity[x] = (parity[x] + parity[pre[x]]) % 2;    //此时pre[x]已指向最终的集合的根
    pre[x] = f;
    return f;
}

bool Query (int x, int y, int odd)
{
    int r1, r2;
    r1 = Find(x);
    r2 = Find(y);
    if ( r1 == r2 )
    {
        if ( (parity[x] + parity[y]) % 2 == odd )
            return true;
        else
            return false;
    }
    else            //只是将r1接到r2下面,这边还可以优化
    {
        pre[r1] = r2;
        parity[r1] = (parity[x] + parity[y] + odd) % 2;
        return true;
    }
}

void Solve ()
{
    int i, x, y, index, idx1, idx2, odd;
    char s[10];
    scanf("%d%d", &n, &p);
    index = 0;
    for (i=0; i<p; i++)
    {
        scanf("%d%d%s", &x, &y, &s);
        x --;
        if ( numIndex.find(x) == numIndex.end() )
            numIndex[x] = index ++;
        idx1 = numIndex[x];
        if ( numIndex.find(y) == numIndex.end() )
            numIndex[y] = index ++;
        idx2 = numIndex[y];
        if ( strcmp(s, "odd") == 0 )
            odd = 1;
        else
            odd = 0;
        if ( Query(idx1, idx2, odd) == false )
        {
            break;
        }
    }
   
    printf("%d\n", i);
}

void Init ()
{
    memset(pre, -1, sizeof(pre));
}

int main ()
{
    Init();
    Solve();

    return 0;
}
posted on 2008-08-15 11:23 quxiao 阅读(1045) 评论(3)  编辑 收藏 引用 所属分类: ACM

评论

# re: PKU 1733 Parity game 2009-01-18 13:02 gugli
Hi from Brazil!

I could not understand your logic because I dont understand chinese.
could you translate to english?

:)

  回复  更多评论
  

# re: PKU 1733 Parity game 2009-01-19 09:47 ACM-Boy
@gugli
This problem is solved by me long time ago, so I can't understand the meaning of the problem very clearly. I just translate the article above code into english.

Tip:
Tell you whether one number between a and b is odd or even, then you can link a line between a-1 and b, the value of the line is determined by whether the number is odd or even. So if you know the state (even or odd) of [1, 2] and [3, 4], of course you know the state of [1, 4].
When the state of [a, b] is given, you find the root of a (r1) and the root of b (r2).
If r1 != r2, it means that the state of [a,b] is not determined. Then link r1 and r2, according to the information that problem give you and the state of a to r1 and b to r2, you can set the value of r1 and r2.
If r1 == r2, it means the state of [a, b] is determined, you can know whether it's true that the state of [a, b] given.

Hope you can understand. Happy new year! :)   回复  更多评论
  

# re: PKU 1733 Parity game 2012-06-16 14:59 TCH
What is your country?@gugli
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理