POJ 1182 食物链 -- 解题报告


食物链














Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 70529 Accepted: 20875

Description

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
动物王国中有三类动物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

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
第一行是两个整数N和K,以一个空格分隔。 

以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。 

若D=1,则表示X和Y是同类。 

若D=2,则表示X吃Y。

Output

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
只有一个整数,表示假话的数目。

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

3

Source

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
Noi 01 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
写在前面 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
——————————- <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
此题为经典并查集,考察的较为全面,这道题算是做了很久都没有思路的类型,之前看别人的博客都不是很理解他们的思路,都是要找规律的,不太懂,并且提交了几次都WA了。看了《挑战程序设计竞赛》中的解方案,豁然开朗,感觉清晰了很多,值得推荐 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
题解 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
——————————- <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
此题的解决方案是对于每只动物创建3个元素,i-A,i-B,i-C,并用3*N个元素创建并查集。 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
i-x表示“i属于种类x” <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
并查集里的每一组表示组内所有元素代表的情况同时发生或者不发生 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>


<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
第一种:x和y属于同一个种类——–合并x-A和y-A,<span style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>x-B和y-B,<span style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>x-C和y-C。 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
第二种:x和y属于不同的种类——–合并x-A和y-B,x-B和y-C,x-C和y-A。 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>


<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
p.s.在合并之前,需要判断合并是否产生矛盾 <div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
#include 
#include

const int maxn = 1e6+7;

int N, K;
int par[maxn], rank[maxn];
int T[maxn], X[maxn], Y[maxn];

void init(int n)
{
for (int i=0; i<=n; i++)
par[i] = i,
rank[i] = 0;
}

int find(int x)
{
return x == par[x] ? x : par[x] = find(par[x]);
}

void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y])
par[x] = y;
else
par[y] = x;
if (rank[x] == rank[y])
rank[x]++;
}

bool same(int x, int y)
{
return find(x) == find(y);
}

void solve()
{
init(N3);
int ans = 0;
for (int i=0; i<K; i++)
{
int t = T[i];
int x = X[i], y = Y[i];
if (x < 1 || y < 1 || x > N || y > N) {
ans++;
continue;
}
if (t == 1) {
if (same(x, y+N) || same(x, y+2
N))
ans++;
else{
unite(x, y);
unite(x+N, y+N);
unite(x+2N, y+2N);
}
}
else {
if (same(x, y) || same(x, y+2N))
ans++;
else {
unite(x, y+N);
unite(x+N, y+2
N);
unite(x+2*N, y);
}
}
}
printf(“%d\n”, ans);
}

int main()
{
scanf(“%d%d”, &N, &K);
for (int i=0; i<K; i++) {
scanf(“%d%d%d”, &T[i], &X[i], &Y[i]);
}
solve();
return 0;
}


坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文作者: Fayne
  • 本文链接: 343.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!