poj 1182 食物链【带权并查集】
2024-08-24 14:56:24
设相等的边权为0,吃的边权为,被吃的边权为2,然后用带权并查集在%3的意义下做加法即可
关系为简单环的基本都可以用模环长的方式是用带权并查集
#include<iostream>
#include<cstdio>
using namespace std;
const int N=50005;
int n,m,f[N],s[N],ans;
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
int zhao(int x)
{
if(x==f[x])
return x;
int nw=zhao(f[x]);
s[x]=(s[x]+s[f[x]]+3)%3;
return f[x]=nw;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
f[i]=i;
while(m--)
{
int d=read()-1,x=read(),y=read();
if(x>n||y>n||(d==1&&x==y))
{
ans++;
continue;
}
int fx=zhao(x),fy=zhao(y);
if(fx!=fy)
{
f[fy]=fx;
s[fy]=(s[x]-s[y]+d+3)%3;
}
else if((s[y]-s[x]+3)%3!=d)
ans++;
}
printf("%d\n",ans);
return 0;
}
最新文章
- bzoj1001最小割
- ES6-Symbol
- php动态生成一个xml文件供swf调用
- apache htaccess
- POJ 1698 (二分图的多重匹配)
- deepin 2014 安装后 ,grub出错
- C指针陷阱
- Nginx+Tomcat+Redis实现持久会话
- day1扩展作业
- Python3 open函数
- TCP三次握手与四次握手
- IO学习
- 安卓基础之Sqlite数据库最最基础操作
- mysql加减时间-函数-时间加减
- SpringMVC 问题 org.springframework.beans.factory.BeanDefinitionStoreException
- springboot的interceptor(拦截器)的应用
- vs code 写C心得
- MongoDB - MongoDB CRUD Operations, Insert Documents
- 【BZOJ 1272】 1272: [BeiJingWc2008]Gate Of Babylon (容斥原理+卢卡斯定理)
- C++标准库 bitset
热门文章
- shell 检查文件夹所属用户组
- 【Objective-C】09-空指针和野指针
- Maven实现Web应用集成測试自己主动化 -- 測试自己主动化(WebTest Maven Plugin)
- poj 2264 Advanced Fruits(DP)
- c# 扩展方法奇思妙用基础篇五:Dictionary<;TKey, TValue>; 扩展
- A Practical Introduction to Blockchain with Python
- C# 软件实现远程桌面调用
- Hive Metastore
- mysql字符串的常用函数(截取和拼接)
- 【转】使用git 工具下载android.jar Source Code