POJ 1386 Play On Words「并查集」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/174

原题地址:点击打开链接

其实本来想做关于欧拉回路的题的,不知道SOJ哪题是欧拉回路的,GOOGLE一下发现说POJ的1386要用欧拉回路。

但是吧……但是吧我怎么做就怎么感觉这题不是欧拉回路。

欧拉通路应该是不重复地经过所有的边1次,即一笔画,欧拉通路和欧拉回路是有点不同的,欧拉通路经过所有的边但不一定(一定不?)回到原点,而欧拉回路则是会回到原点的。

这条题目网上很多人写解答,都是说欧拉回路/欧拉通路……為什麼我还是看不出哪里用到了欧拉路呢

——————正文——————

什么情况下可以输出Possible呢?满足以下两个充要条件即可:

1.   a.所有字母出现在单词首与单词尾的次数一样或者  b.有其中两个字母不一样,两个字母中其中一个出现在单词头的次数比出现在单词尾的次数多1,另外一个出现在单词尾的次数比出现在单词头的次数多1

2.  利用并查集可以发现所有的单词首尾字母都在一个集合中。

现在一个严峻的问题就是——为虾米上面两个是充要条件!!??如何证明?

——证明——

条件1:

对于任何满足条件的序列,假设是a1,a2,a3,…,an,假设对于任何一个字母进行计数(假设字母是a),若a出现在尾部,计数器counter_a就减1,出现在首部,计数器counter_a就加1,那么以下这个字符集合中,所有字符(a~z)的counter经过计算最终都为0:a1的尾字母+a2~a(n-1)的首尾字母+an的首字母。而a1的首字母不一定和an的尾字母相同,所以最终的某个字母的counter可能会出现1或者-1。因此不满足上面条件1的序列,肯定是不符合要求的。

条件2:

但是仅仅满足条件1是不够的,因为很容易可以构造出一个序列满足条件1,但是不是符合要求的序列,例如:

情况1:aaa+bbb,或者说abb+bba+ccd+dcc。这种情况下实际可以将能够连在一起的单词看成一个整体(即1个单词),1个单词的首字母和尾字母相同,导致计数器为0,但实际上序列不合法。

情况2:通过情况1,我们知道序列不合法时最少会有2个“单词(此处指组合后的单词)”,设为word1和word2,那么word1的首字母不等于word2的尾字母,同时word1的尾字母不等于word2的首字母,大家可以经过暴力尝试(也就8种情况)发现,无论怎么组合,除了情况1外,其它都会违反条件1,所以我们只需要考虑在满足条件1的情况下,如何排除情况1。

要排除情况1,就像之前所说的,使用并查集即可,判断所有的字母都在一个集合中,或许会有人问会不会出现这么一个情况:在满足条件1的情况下,假设word1的集合已经建立好了,那么word2会不会出现某些字母在word1的集合里?不会,首先满足了条件1,那么要么是合法的序列(这样就不会有word1和word2),要么是情况1的序列,如果是情况1的序列,那么word1的首尾字母是相同的,word2的首尾字母也是相同的,word2的字母如果出现在word1的集合里,那么就表明word1和word2可以拼接起来,首先将word1从该字母处断开,变成word1_1和word1_2,然后word2也从这个字母的地方断开,变成word2_1和word2_2,然后,拼接的顺序是——word1_1+word2_2+word2_1+word1_2,word2_2和word2_1可以拼接是因为word2的首尾字母相同。

——得证——

费了这么大的力,终于就证明了这个充要条件,是充要条件啊……做题的时候,很多人可以凭感觉就觉得应该是这样的,应该就是条件1和条件2构成了重要条件,然后直接做一下就AC了,我也是感觉是这样,但是做完后十分的不放心,这个為什麼是对的?想起《编程之美》里面以及《暗时间》里面都讲到了“知其所以然”的重要性,我也就不敢懈怠了。

上面的证明过程可能不严谨,但是方向是这样的,也已经具有一定的说服力,如果哪位朋友发现什么问题,欢迎指出。

最后贴上代码,如下:

#include<stdio.h>
#include<cstring>
#include<memory.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 100005
using namespace std;
struct node
{
    char bb,ee;
}nn[MAXN];
int n,tc;
int bal[150];
int p[150];
char ss[1500];
void printR(bool can)
{
    if(can)
     printf("Ordering is possible.\n");
    else
     printf("The door cannot be opened.\n");
}
int parent(int index)
{
    if(p[index]==index)
     return index;
    else
     return p[index]=parent(p[index]);
}
int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    cin>>tc;
    while(tc--) 
    {
        memset(bal,0,sizeof(bal));
        cin>>n;
        for(int i=0;i<n;++i)
        {
          scanf("%s",ss);
          nn[i].bb=ss[0];
          nn[i].ee=ss[strlen(ss)-1];
          bal[nn[i].bb]++;
          bal[nn[i].ee]--;
          p[nn[i].bb]=nn[i].bb;
          p[nn[i].ee]=nn[i].ee;
        }
        int cnt=0;
        bool _1vis=false;  //首字母出现次数多1的是否已经有了
        bool _m1vis=false; //尾字母出现次数多1的是否已经有了
        for(int i='a';i<='z'&& !cnt;i++)
        {
             if(abs(bal[i])>1)
               cnt=105;      //给错误情况赋值有利用于DEBUG
             
             else if(bal[i]==1) {
               if(_1vis)
                  cnt=101;
               else
                  _1vis=true;
             }
             else if(bal[i]==-1) {
                if(_m1vis)
                  cnt=100;
                else
                  _m1vis=true;
             }
        }
        if(cnt)
        { 
            printR(0);
            continue;
        }
        
        for(int i=0;i<n;++i)
         p[nn[i].ee]=parent(nn[i].bb);
        
        cnt=parent(nn[0].ee);
        for(int i=0;i<n;++i)
         if(parent(nn[i].bb)!=cnt || parent(nn[i].ee)!=cnt)
         {
             cnt=0;
             break;
         }

        if(cnt)
         printR(1);
        else
         printR(0);
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注