POJ1182 | 哈喽哈咯

Written by razrlele 21:57 December 13, 2016

食物链

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 66244		Accepted: 19522

Description

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

Input

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

Output

只有一个整数，表示假话的数目。

Sample Input

100 7

1 101 1

2 1 2

2 2 3

2 3 3

1 1 3

2 3 1

1 5 5

Sample Output

Source

Noi 01

思路

大概思路就是要用到并查集，但是这道题里面N和K的值都很大，并且不只有属于同一类的信息，还有捕食关系的存在，所以维护这些关系又是个难题。在《挑战程序设计竞赛》上有关于这道题的一个有意思的解法：对于每只动物i创建3个元素i-A,i-B,i-C，并且用3*N个元素建立并查集，这个并查集维护以下信息：

i-x表示「i属于种类x」。
并查集里面的每一个集合表示所有元素代表的情况都同时发生或同时不发生。

例如，如果i-A和j-B在同一个组里，就表示如果i属于种类A那么j一定属于种类B，如果j属于种类B那么i一定属于种类A。因此，对于每一条信息，只需要按照下面进行操作即可：

第一种，x和y属于同一种类，就合并x-A和y-A, x-B和y-B，x-C和y-C。
第二种，x吃y，就合并x-A和y-B, x-B和y-C，x-C和y-A。

在合并之前还需要判断是否会产生矛盾。

另外这个题比较坑的地方居然是不能循环输入，之前写算法题的时候都养成习惯开头就while(cin…主要是为了方便测试多组数据，然后再这道题目里面就会WA，还有就是数据IO比较大，所以用cin也容易超时。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

* File Name: poj1182.cpp

* Author: razrLeLe

* Mail: razrlele@gmail.com

#include <vector>

#include <set>

#include <deque>

#include <queue>

#include <algorithm>

#include <functional>

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <string>

#include <cstring>

#include <string.h>

#include <map>

#include <cctype>

#include <list>

#include <stack>

#define ll long long

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

const int maxn = 50007;

int par[maxn*3];

int R[maxn*3];

void init(int n){

for(int i = 0; i < n; i++){

par[i] = i;

R[i] = 0;

}

int find(int x) {

if(par[x] == x){

return x;

} else {

return par[x] = find(par[x]);

}

void unite(int x, int y) {

x = find(x);

y = find(y);

if (x == y) return ;

if( R[x] < R[y]){

par[x] = y;

} else {

par[y] = x;

if( R[x] == R[y]) R[x]++;

}

bool same(int x, int y){

return find(x) == find(y);

}

// Define union-find above.

int N, K;

int D[maxn*2], X[maxn*2], Y[maxn*2];

void solve(){

init(N*3);

int ans = 0;

for(int i= 0; i < K; i++){

int d = D[i];

int x = X[i]-1, y = Y[i]-1;

if( x < 0 || x >= N || y < 0 || y >= N){

ans++;

continue;

}

if( d == 1){

if( same(x, y+N) || same(x, y+2*N)){

ans++;

}

else{

unite(x, y);

unite(x+N, y+N);

unite(x+2*N, y+2*N);

}

else{

if(

same(x, y) || same(x, y+2*N)

// ||

// same(x+N, y+N) || same(x+N, y)

// ||

// same(x+2*N, y+N) || same(x+2*N, y+2*N)

){

ans++;

}

else{

unite(x, y+N);

unite(x+N, y+2*N);

unite(x+2*N, y);

}

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

}

int main(int argc, char ** argv)

{

#ifdef LOCAL

freopen("/Users/yuyue/build/data.txt", "r", stdin);

//freopen("/Users/yuyue/build/out.txt", "w", stdout);

#endif

scanf("%d %d", &N, &K);

for(int i = 0; i < K; i++){

scanf("%d %d %d", &D[i], &X[i], &Y[i]);

}

solve();

return 0;

}