首页 > 代码库 > POJ1291 This Sentence is False (并查集 || 哈希）

POJ1291 This Sentence is False (并查集 || 哈希）

2024-07-15 00:54:35   219人阅读

本文出自：http://blog.csdn.net/svitter


写在之前：

最近感觉做了不少的并查集的题目。发现A说B说的对，谁说假话谁说真话这种游戏，基本全是并查集。做下记录，防止以后忘记。


题意：

题目给出n句话，编号从1开始。每一句话都是类似：Sentence $num is true/false 这种形式。

最后输出真话最多的情况的真话个数。

输入输出分析：

注意scanf的格式，不能使用"Sentence %d is %s"这种格式。具体原因未知。可以使用%s不停的读入到不用的变量中来消除缓存区中的字符。

算法数据结构分析：

首先利用i， i+n这种取反的方法来判断对错。如果出现悖论，继续吸收缓冲区，但是不在进行计算。

具体方法可以参见:POJ2492 A Bug‘s Life （并查集）

求出相应集合以后，统计num[getRoot(i)]的个数，最后相加即可。

问题：

一开始连着getRoot(i+n)我也统计了，后来参照了大神的代码，考虑到i+n的情况属于i的对立情况，没有必要计算.

与i对立的情况必定是包含在除了i的情况中，所以没有必要进行统计。

在遍历num数组的过程中，取num[getRoot(i)]和num[getRoot(i+n)]中较大的一组。即：取i或者～i。因为不存在悖论，所以i和～i必定有一个成立。


AC代码：

//author: svtter
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

#define INF 0xffffff

using namespace std;
int root[2010];
int n;
int num[2010];
int vis[2010];

void init()
{
    for(int i = 0; i <= n*2; i++)
        root[i] = i;
}

int getRoot(int i)
{
    if(i == root[i])
        return i;
    return root[i] = getRoot(root[i]);
}

int a, b;
void Merge(int i, int j)
{
    a = getRoot(i);
    b = getRoot(j);
    if(a == b)
        return;
    root[a] = b;
}

bool jud(int i, int j)
{
    return getRoot(i) == getRoot(j);
}

void solve()
{
    int i, ans; 
    ans = 0;
    memset(num, 0, sizeof(num));
    memset(vis, 0, sizeof(vis));

    for(i = 1; i <= n; i++)
    {
        num[getRoot(i)] ++;   
        // num[getRoot(i+n)]++;
    }
    
    for(i = 1; i <= n; i++)
    {
        if(vis[getRoot(i)] || vis[getRoot(i+n)])
            continue;
        ans += max(num[getRoot(i)], num[getRoot(i+n)]);
        vis[getRoot(i)] = vis[getRoot(i+n)] = 1;
    }

    printf("%d\n", ans);
}

int main()
{
    char ju[10];
    int i, t;
    bool paradox;
    while(~scanf("%d", &n))
    {
        if(n == 0)
            break;
        paradox = false;
        //input
        init();
        for(i = 1; i <= n; ++i)
        {
            scanf("%s", ju);
            scanf("%d", &t);
            scanf("%s", ju);
            scanf("%s", ju);

            if(paradox)
                continue;
            if(ju[0] == 'f')
            {
                if(jud(i, t) || jud(i+n, t+n))
                    paradox = 1;
                else
                {
                    Merge(i, t+n);
                    Merge(t, i+n);
                }
            }
            else
            {
                if(jud(i, t+n) || jud(t, i+n))
                    paradox = 1;
                else
                {
                    Merge(i, t);
                    Merge(i+n, t+n);
                }
            }
        }
        if(paradox)
            printf("Inconsistent\n");
        else
            solve();
    }
    return 0;
}



联系
我们