题解:洛谷P1955:[NOI2015]程序自动分析

发布于 / 题解 / 0 条评论

题目描述

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设 x_1,x_2,x_3\dots代表程序中出现的变量,给定 n 个形如x_i=x_jx_i \neq x_j的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

输入格式

从文件prog.in中读入数据。

输入文件的第 1 行包含 1 个正整数 t,表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

1 行包含 1 个正整数 n ,表示该问题中需要被满足的约束条件个数。接下来 n 行,每行包括 3 个整数 i,j,e,描述 1 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 e=1,则该约束条件为 xi=xj;若 e=0,则该约束条件为 xi\neq xj

输出格式

输出到文件 prog.out 中。

输出文件包括 t 行。

输出文件的第 k 行输出一个字符串“ YES” 或者“NO”(不包含引号,字母全部大写),“YES” 表示输入中的第 k 个问题判定为可以被满足,“NO” 表示不可被满足。

输入输出样例

输入 #1

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出 #1

NO
YES

输入 #2

2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

输出 #2

YES
NO

说明/提示

【样例解释1】

在第一个问题中,约束条件为:x1=x2,x1\neq x2。这两个约束条件互相矛盾,因此不可被同时满足。

在第二个问题中,约束条件为:x1=x2,x1=x2。这两个约束条件是等价的,可以被同时满足。

【样例说明2】

在第一个问题中,约束条件有三个:x1=x2,x2=x3,x3=x1。只需赋值使得x1=x1=x1,即可同时满足所有的约束条件。

在第二个问题中,约束条件有四个:x1=x2,x2=x3,x3=x4,x4\neq x1。由前三个约束条件可以推出x1=x2=x3=x4,然而最后一个约束条件却要求x1\neq x4,因此不可被满足。

【数据范围】

【时限2s,内存512M】

题目传送门:🚪

文件读入与写出

虽说题干写着从文件读入,写出到文件,但其实这个题完全不需要……直接标准读入读出就可以……可怜我太实诚……酿造了如下惨状:

既然提到了就说说这个……

C的方法

  • fopen()函数

    使用方式:fp = fopen("input.in", "r")

    • 第一个参数为打开文件的文件名;
    • 第二个参数为文件方式,是文件的类型和操作要求,有如下几种(组合):
    • r:只读(read),要求文件必须已经存在;
    • w:只写(Write),若文件不存在则自动创建,如果已存在则删除原文件后新建;
    • a:追加(Append),保留文件中已有内容,从文件尾开始写;
    • t:文本文件(Text),可忽略;
    • b:二进制文件(Binary);
    • +:读写。
    • 返回值为文件指针,为FILE类型的指针变量。

    在具体使用此方法写入时,使用fscanf(fp, "%d", &n)来读取:

    • 第一个参数为文件指针名,即使用fopen返回的指针;
    • 第二个参数为格式控制符,同scanf()的使用方式;
    • 第三及以后的参数为传入变量的指针。

    使用fprintf(fp, "%d\n", n)来写入文件:

    • 第一个参数为文件指针名,即使用fopen返回的指针;
    • 第二个参数为格式控制符,同printf()的使用方式;
    • 第三及以后的参数为输出变量。

    结束使用该函数使用:fclose(fp)

  • freopen()函数

    使用方式:freopen("input.in", "r", stdin);freopen("output.out", "w", stdout);

    • 第一个参数为打开文件的文件名;
    • 第二个参数为文件方式,同fopen()函数;
    • 第三个参数为文件指针,通常使用标准流文件(stdin/stdout/stderr)。

    使用freopen()函数,并使用了标准流文件后,就可以直接使用scanf()printf()来读入和写出。

    结束使用fclose(stdin);fclose(stdout)

C++的方法

ifstream inputFL("input.in");
ofstream outputFL("putput.out");
inputFL >> n;
outputFL << n << endl;
inputFL.close();
outputFL.close();

正式题解

基本题意就是给你几个约束条件看他们能不能共存成立。而相等关系的约束条件我们可以很容易地想到将其转换为一个图,出现相等关系就说明它们在一个个图上 \Rightarrow 两个值的最终祖先节点相同。而出现不等关系就说明它们没在一个图上,所以这个问题就可以转换成一个并查集问题。在这里贴上并查基常用的板子:

  • 得到最终祖先:
    int get(int x){
      if(x == fa[x]){
          return x;
      }else return fa[x] = get(fa[x]);
    }
    
  • 合并两棵树:
    void merge(int a, int b){
      int faOa = get(a);
      int faOb = get(b);
      if(faOa != faOb){
          fa[b] = a;
      }
    }
    

而注意到题目数据量很大,ij 的范围到了 10^9,无法开那么大的数组,所以我们使用到了离散化。我的离散化的博文的传送门:🚪

基本思想就是看输入的两个值是否相同,如果相同就保留到一棵树上。如果不相同的话检查两个点的根结点是否相同,如果相同则说明这两个值已经相同,出现矛盾,则输出“NO”。为了实现这个思想,我们首先要对输入进行排序,将相等关系放在前面预先判断。

AC代码如下:

#include <bits/stdc++.h>
#define inputFL cin
#define outputFL cout
using namespace std;
struct Node{
    int x;
    int y;
    bool e;
}Nodes[100005];
bool cmp(Node a, Node b){
    return a.e > b.e;
}
int dict[1000005];
int fa[1000005];
int cnt, uqcnt;
int n;
int get(int x){
    if (x == fa[x]) {
        return x;
    }else return fa[x] = get(fa[x]);
}
// void merge(int x, int y){
//     fa[get(x)] = get(y);
// }
int main(){
    // ifstream inputFL("prog.in"); // C++方式, C使用freopen()
    // ofstream outputFL("prog.out");
    int T;
    inputFL >> T;
    while(T--){
        inputFL >> n;
        memset(dict, 0, sizeof(dict));
        memset(fa, 0, sizeof(fa));
        uqcnt = cnt = 0;
        for (int i = 0; i < n; i++) {
            inputFL >> Nodes[i].x >> Nodes[i].y >> Nodes[i].e;
            dict[cnt++] = Nodes[i].x;
            dict[cnt++] = Nodes[i].y;
        }
        sort(dict, dict + cnt);
        uqcnt = unique(dict, dict + cnt) - dict;
        for (int i = 0; i < n; i++) {
            Nodes[i].x = lower_bound(dict, dict + uqcnt, Nodes[i].x) - dict;
            Nodes[i].y = lower_bound(dict, dict + uqcnt, Nodes[i].y) - dict;
        }
        for (int i = 0; i < uqcnt; i++) {
            fa[i] = i;
        }
        bool check = 1;
        sort(Nodes, Nodes + n, cmp);
        for (int i = 0; i < n; i++) {
            int a = get(Nodes[i].x);
            int b = get(Nodes[i].y);
            if (Nodes[i].e) {
                fa[a] = b;
            }else{
                if (a == b) {
                    check = 0;
                    outputFL << "NO" << endl;
                    break;
                }
            }
        }
        if (check)
            outputFL << "YES" << endl;
    }
}

特别提醒:一定要分清离散化中各个变量的具体含义与用处,否则就会出现以下的状况而无从下手:

转载原创文章请注明,转载自: KONGJUNE » 题解:洛谷P1955:[NOI2015]程序自动分析
Not Comment Found