首页 > 专题系列 > Java解POJ > POJ 1291 This Sentence is False [解题报告] Java
2013
11-09

POJ 1291 This Sentence is False [解题报告] Java

This Sentence is False

问题描述 :

The court of King Xeon 2.4 is plagued with intrigue and conspiracy. A document recently discovered by the King’s Secret Service is thought to be part of some mischievous scheme. The document contains simply a set of sentences which state the truth or falsehood of each other. Sentences have the form “Sentence X is true/false” where X identifies one sentence in the set. The King’s Secret Service suspects the sentences in fact refer to another, yet uncovered, document.

While they try to establish the origin and purpose of the document, the King ordered you to find whether the set of sentences it contains is consistent, that is, if there is a valid truth assignment for the sentences. If the set is consistent, the King wants you to determine the maximum number of sentences which can be made true in a valid truth assignment for the document.

输入:

The input contains several instances of documents. Each document starts with a line containing a single integer,

N, which indicates the number of sentences in the document (1 <= N <= 1000). The following N lines contain each a sentence. Sentences are numbered sequentially, in the order they appear in the input (the first is sentence 1, the second is sentence 2, and so on). Each sentence has the form "Sentence X is true." or "Sentence X is false.", where 1 <= X <= N. The value N = 0 indicates the end of input.

输出:

For each document in the input your program should output one line. If the document is consistent,your program should print the maximum number of sentences in a valid truth assignment for the document.Otherwise your program should print the word ‘Inconsistent’.

样例输入:

1
Sentence 1 is false.
1
Sentence 1 is true.
5
Sentence 2 is false.
Sentence 1 is false.
Sentence 3 is true.
Sentence 3 is true.
Sentence 4 is false.
0

样例输出:

Inconsistent
1
3

解题代码:

//* @author: Yeming Hu"[email protected]"
import java.util.*;
import java.io.BufferedInputStream;

public class Main
{
    public static Node[] nodes;
    
    public static void main(String[] args) 
    {
      Scanner sc = new Scanner(new BufferedInputStream(System.in));
      while(true)
      {
            int n = sc.nextInt();
            if(n == 0)
            {
                break;
            }
            boolean consistent = true;
            nodes = new Node[n+1];
            for(int i = 1; i <= n; i++)//make set;
            {
                nodes[i] = new Node(i);
            }
            for(int i = 1; i <=n; i++)
            {
                sc.next();
                int j = sc.nextInt();
                sc.next();
                String falsehood = sc.next();
                falsehood = falsehood.substring(0,falsehood.length()-1);
                if(consistent)
                {
                    boolean unionOk = unionOne(i,j,Boolean.parseBoolean(falsehood));
                    if(!unionOk)
                    {
                        consistent = false;
                    }
                }
            }
            if(consistent)
            {
                int result = 0;
                for(int i = 1; i <= n; i++)
                {
                    if(nodes[i].parent == -1)
                    {
                        if(nodes[i].numOfTrue >= nodes[i].numOfFalse)
                        {
                            result += nodes[i].numOfTrue;
                        }else
                        {
                            result += nodes[i].numOfFalse;
                        }
                    }
                }
                System.out.println(result);
            }else
            {
                System.out.println("Inconsistent");
            }
        }
    }
    
    public static boolean unionOne(int i, int j, boolean falsehood)
    {
        int t1 = find(i);
        int t2 = find(j);
        boolean unionOk = true;
        if(t1 == t2)
        {
            if( (nodes[i].falsehood == true) != (nodes[j].falsehood == falsehood) )
            {
                unionOk = false;
            }
        }else
        {
            if(nodes[t2].num <= nodes[t1].num)
            {
                nodes[t2].parent = t1;
                /*for(int k : nodes[t2].nodes)
                {
                    nodes[k].parent = t1;
                }*/
                nodes[t1].num += nodes[t2].num;
                if( (nodes[i].falsehood == true) != (nodes[j].falsehood == falsehood) )
                {
                    for(int k : nodes[t2].nodes)
                    {
                        nodes[k].falsehood = !nodes[k].falsehood;
                    }
                    nodes[t1].numOfTrue += nodes[t2].numOfFalse;
                    nodes[t1].numOfFalse += nodes[t2].numOfTrue;
                }else
                {
                    nodes[t1].numOfTrue += nodes[t2].numOfTrue;
                    nodes[t1].numOfFalse += nodes[t2].numOfFalse;
                }
                
                nodes[t1].nodes.addAll(nodes[t2].nodes);
            }else
            {
                nodes[t1].parent = t2;
                /*for(int k : nodes[t1].nodes)
                {
                    nodes[k].parent = t2;
                }*/
                nodes[t2].num += nodes[t1].num;
                if( (nodes[i].falsehood == true) != (nodes[j].falsehood == falsehood) )
                {
                    for(int k : nodes[t1].nodes)
                    {
                        nodes[k].falsehood = !nodes[k].falsehood;
                    }
                    nodes[t2].numOfTrue += nodes[t1].numOfFalse;
                    nodes[t2].numOfFalse += nodes[t1].numOfTrue;
                }else
                {
                    nodes[t2].numOfTrue += nodes[t1].numOfTrue;
                    nodes[t2].numOfFalse += nodes[t1].numOfFalse;
                }
                nodes[t2].nodes.addAll(nodes[t1].nodes);
            }
        }
        return unionOk;
    }
    
    public static int find(int x)
    {
        Node r = nodes[x];
        while(r.parent != -1)
        {
            r = nodes[r.parent];
        }
        while(nodes[x].position != r.position)
        {
            int q = nodes[x].parent;
            nodes[x].parent = r.position;
            x = q;
        }
        return r.position;
    }
    
}

class Node
{
    int position;
    boolean falsehood;
    int parent;
    int num;
    int numOfTrue;
    int numOfFalse;
    LinkedList nodes;
    
    public Node(int position)
    {
        this.position = position;
        this.falsehood = true;
        this.parent = -1;
        this.num = 1;
        this.numOfTrue = 1;
        this.numOfFalse = 0;
        this.nodes = new LinkedList< Integer>();
        this.nodes.add(position);
    }
}

  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  3. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  4. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!