社区讨论
为什么用了快读还是90分
P2024[NOI2001] 食物链参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo90ps7i
- 此快照首次捕获于
- 2023/10/28 03:40 2 年前
- 此快照最后确认于
- 2023/10/28 03:40 2 年前
CPP
cpp
//种类并查集
//种类并查集求的并非具体种类,而是关系!
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,a,b,c,ans=0,cnt=0;
int fa[N];
map <string,int> mp;
inline int read()
{
char c = getchar(); int n = 0;
while (c < '0' || c > '9') { c = getchar(); }
while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
return n;
}
int find(int x)//找x的根节点
{
if(x == fa[x]) return x;
else return fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
fa[find(x)] = find(y);//找到y的根节点和x的根节点,并把它连起来
}
int main()
{
// cin>>n>>m;
n=read();
m=read();
for(int i=1;i<=3*n;i++)
fa[i]=i;
while(m--)
{
// cin>>a>>b>>c;
a=read();
b=read();
c=read();
if(b>n || c>n)//不要忘了特判编号大于 n 的情况!
{
ans++;
continue;
}
if(a==1)
{
//错误点1:如果直接判,那么本来每个元素的根都是他自己,所以ans++永远成立
// if((find(b) == find(c)) || (find(b+n) == find(c+n)) || (find(b+2*n) == find(c+2*n)))
// {
// merge(b,c);
// merge(b+n,c+n);
// merge(b+2*n,c+2*n);
// }
// else ans++;
if(find(b)==find(c+n) || find(b) ==find(c+2*n))
ans++;
else
{
merge(b,c);
merge(b+n,c+n);
merge(b+2*n,c+2*n);
}
}
if(a==2)
{
// if((find(b) == find(c+n)) || (find(b+n) == find(c+2*n)) || (find(b+2*n) == find(c)))
// {
// merge(b,c+n);
// merge(b+n,c+2*n);
// merge(b+2*n,c);
// }
// else ans++;
//错误点2:如果直接判,那么本来每个元素的根都是他自己,所以ans++永远成立
if(find(b) == find(c) ||find(b) == find(c+2*n)) ans++;
else
{
merge(b,c+n);
merge(b+n,c+2*n);
merge(b+2*n,c);
continue;
}
}
// cout<<cnt<<" "<<"ans="<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...