现在的位置: 首页 > 综合 > 正文

poj 2513 Colored Sticks

2014年09月05日 ⁄ 综合 ⁄ 共 2641字 ⁄ 字号 评论关闭

题目的意思是:给定一些木棒,木棒两端都涂上颜色,求是否能将木棒首尾相接,连成一条直线,要求不同木棒相接的一边必须是相同颜色的。

首先这是一个环而且两边的颜色一样啊,所以抽象出来就是经过每个边一次,且仅且一次,这就是离散数学中的欧拉回路了啊、、但是这是颜色是字符串所以又用到了啊字典树查颜色的个数、、。。

我在这里也叙述的不太清楚详情还是看ζёСяêτ - 小優YoU的博客吧、、 http://blog.csdn.net/lyy289065406/article/details/6647445

基本方法:

初始化所输入的n个结点为n棵树,那么就有一个n棵树的森林,此时每棵树的有唯一的结点(根),该结点的祖先

它本身。再通过不断地输入边,得到某两个结点(集合)之间的关系,进而合并这两个结点(集合),那么这两

个集合就构成一个新的集合,集合内的所有结点都有一个共同的新祖先,就是这个集合(树)的根。

最后只要枚举任意一个结点,他们都具有相同的祖先,那么就能证明图时连通的了。
 
但是单纯使用并查集是会超时的,因为这样会导致每次寻找某个结点的祖先时,平均都会花费O(n/2)时间,最坏情

况,当n==50W时,O(n/2)大概为25ms,那么要确定50W个结点是否有共同祖先时,总费时为50W*25ms ,铁定超

,不算了= =
 
因此必须使用并查集时必须压缩路径,前几次搜索某个结点k的祖先时,在不断通过父亲结点寻找祖先结点时,顺便

把从k到最终祖先结点S中经过的所有结点的祖先都指向S,那么以后的搜索就能把时间降低到O(1)
 

由于并查集必须利用 数组的下标 与 存储的对象,使用int是比较方便的处理方法,但是题目的“颜色结点”是string,不

方便用来使用并查集,即使用map也不行,虽然STL的map是基于hash的基础上,但并不高效,在本题中使用会超时。

 
为此可以使用Trie字典树,得到每个颜色单词对应的int编号id ,可以说利用Trie把string一一映射到int,是本题后续处

理的关键所在。关于动态创建字典树的方法去百度,这里不多说,下面只用用一个图简单说明一下用Trie字典树标识

第一个颜色单词blue:

Colored Sticks
Time Limit: 5000MS   Memory Limit: 128000K
Total Submissions: 27840   Accepted: 7356

Description

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

Input

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

Output

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#define N 500010

using namespace std;

struct node
{
    int flag, id;
    struct node*next[26];
};
struct node*root;
int color = 0;
int degree[N] = {0};
int f[N];
int find(int x)
{
    while(f[x] != x)
        x = f[x];
    return x;
}

void union_set(int a, int b)
{
    int x = find(a);
    int y = find(b);
    f[y] = x;
    return;
}
int bulid(char s[])
{
    int i, j, k, t;
    struct node*p;
    p = root;
    k = strlen(s);
    for(i = 0; i < k; i++)
    {
        t = s[i]-'a';
        if(p->next[t] == NULL)
        {
            p->next[t] = (struct node*)malloc(sizeof(struct node));
            for(j = 0; j < 26; j++)
                p->next[t]->next[j] = NULL;
            p->next[t]->flag = 0;
        }
        p = p->next[t];
    }
    if(p->flag)
        return p->id;
    else
    {
        p->flag = 1;
        p->id = ++color;
        return p->id;
    }
}
int main()
{
    for(int k = 1; k <= N-10; k++)
        f[k] = k;
    char a[12], b[12];
    root = (struct node*)malloc(sizeof(struct node));
    for(int i = 0; i < 26; i++)
        root->next[i] = NULL;
    root->flag = 0;
    while(cin >>a>>b)
    {
        int i = bulid(a);
        int j = bulid(b);
        degree[i]++;
        degree[j]++;
        union_set(i,j);
    }
    int s = find(1);
    int num = 0;
    for(int i = 1; i <= color; i++)
    {
        if(degree[i]%2 == 1)
            num++;
        if(num>2)
        {
            cout<<"Impossible"<<endl;
            return 0;
        }
        if(find(i)!=s)
        {
            cout<<"Impossible"<<endl;
            return 0;
        }
    }
    if(num==1)
        cout<<"Impossible"<<endl;
    else
        cout<<"Possible"<<endl;
    return 0;
}

抱歉!评论已关闭.