POJ1182 食物链---(经典种类并查集)
2024-09-22 08:11:20
食物链
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 69207 | Accepted: 20462 |
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),输出假话的总数。
现有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。
以下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
3
Source
分析与总结:
这题是稍微复杂的种类并查集, 共有3种动物,那么显然就应该分为3类。
假设x 吃 y, 那么x比y的权值大1.因为共有3种动物,那么权值要分为0,1,2三种。0是根结点, 如果有个节点的权值是1,就表示这个结点是吃根结点的,如果权值是2,表示2是吃1的(2比1大1),而因为三种动物循环吃的关系, 2 也就是被0吃的。
然后在合并时,按照关系分类计算它们的权值。
#include <stdio.h> /** father[x]表示x的根节点 */
int father[]; /**
rank[x]表示father[x]与x的关系
rank[x] == 0 表示father[x]与x是同类
rank[x] == 1 表示x吃father[x]
rank[x] == 2 表示father[x]吃x
*/
int rank[]; /** 初始化集合 */
void Make_Set(int x)
{
father[x] = x;
} /** 查找x所在的集合 */
int Find_Set(int x)
{
int t;
if (father[x] == x) return x;
t = father[x];
father[x] = Find_Set(father[x]);
/** 因为压缩时根节点改变,必须更新father[x]与x的关系 */
rank[x] = (rank[t] + rank[x]) % ;
return father[x];
} /** 合并a和b */
void Union_Set(int a, int b, int len)
{
int ra = Find_Set(a);
int rb = Find_Set(b);
/** 将集合ra合并到集合rb上 */
father[ra] = rb;
/** 更新father[ra]与ra的关系 */
rank[ra] = (rank[b] - rank[a] + + len) % ;
} int main()
{
int i, n, m;
int d, x, y;
int rx, ry;
int sum = ;
scanf("%d%d", &n, &m);
for (i = ; i <= n; i++)
{
Make_Set(i);
}
while(m--)
{
scanf("%d%d%d", &d, &x, &y);
if (x > n || y > n || (d == && x == y))
{
sum++;
}
else
{
/** 求出x和y所在的集合rx和ry */
rx = Find_Set(x);
ry = Find_Set(y);
/** 若在同一个集合则可确定x和y的关系 */
if (rx == ry)
{
if((rank[x] - rank[y] + ) % != d - )
{
sum++;
}
}
/** 无法确定关系时按照规则合并节点 */
else
{
Union_Set(x, y, d - );
}
}
}
printf("%d\n", sum);
return ;
}
挑战编程
/**
poj1182食物链
并查集应用题
并查集是维护“属于同一组” 的数据结构
本题不只有属于同一类关系,还有捕食关系
对于每只动物i创建3个元素,i-A,i-B,i-C并用这3*N个元素建立并查集(i-X表示i属于X)
1.x y为同一类,合并x-A x-B x-C
*/
#include "cstdio"
#define maxn 50007
int n,k;
int set[maxn*],r[maxn*];
int d[maxn*],x[maxn*],y[maxn*];
int findFa(int x)
{
if(x==set[x])
return x;
else
{
return set[x]=findFa(set[x]);
}
}
void init(int n)
{
for(int i=;i<n;i++)
{
set[i]=i;
r[i]=;
}
}
void Unite(int x,int y)
{
int a=findFa(x);
int b=findFa(y);
if(x==y)
return ;
if(r[a]<r[b])
{
set[a]=b;
}else
{
set[b]=a;
if(r[a]==r[b])r[a]++;
}
}
bool same(int x,int y)
{
return findFa(x)==findFa(y);
}
void solve()
{
init(*n);
int ans=;
for(int i=;i<k;i++)
{
int dd=d[i],xx=x[i]-,yy=y[i]-;
if(xx<||yy<||xx>=n||yy>=n)
{
ans++;continue;
}
if(dd==)
{
if(same(xx,yy+n)||same(xx,yy+*n))
{
ans++;
}
else
{
Unite(xx,yy);
Unite(xx+n,yy+n);
Unite(xx+*n,yy+*n);
}
}
else
{
if(same(xx,yy)||same(xx,yy+*n))
{
ans++;
}
else
{
Unite(xx,yy+n);
Unite(xx+n,yy+*n);
Unite(xx+*n,yy);
}
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<k;i++)
{
scanf("%d%d%d",&d[i],&x[i],&y[i]);
}
solve();
}
最新文章
- 数据库 之MySQL 简单教程
- 003_kafka_主要配置
- javascript模块化详解
- 大S《美容大王》内容80%都是没用的东西
- 配置安装theano环境(非GPU版)
- thinkphp 配置
- [x-means] 1.x-means简介
- poj3090--欧拉函数
- Vue阻止冒泡
- bootstrap 鼠标悬停显示
- CentOS7中关闭firewall,并使用iptables管理防火墙
- django搭建web (二) urls.py
- 自动化运维:使用flask+mysql+highcharts搭建监控平台
- java--序列化和反序列化
- java微信获取经纬度转换为高德坐标小结
- 分布式事务、多数据源、分库分表中间件之spring boot基于Atomikos+XADataSource分布式事务配置(100%纯动态)
- p3792 由乃与大母神原型和偶像崇拜(思维+线段树)
- 生成本地测试用https证书,支持通配符和多域名,初学OpenSSL
- 《Macro-Micro Adversarial Network for Human Parsing》论文阅读笔记
- VS文件发布不了,这样设置可以解决