「NOI2001」食物链

传送门

Luogu

解题思路

带权并查集我不会啊

考虑种类并查集（扩展域并查集的一种）。

开三倍空间，一倍维护本身，二倍维护猎物，三倍维护天敌，然后用并查集搞一搞就好了。

细节注意事项

咕咕咕

参考代码

#include<bits/stdc++.h>

using namespace std;

const int maxN=100005;

int n,m,ans,fa[maxN*3];

int find(int u){

	return fa[u]==u?u:fa[u]=find(fa[u]);

}

int main(){

	cin>>n>>m;

    for(int i=1;i<=n*3;i++)fa[i]=i;

    while(m--){

    	int opt,u,v;

    	cin>>opt>>u>>v;

        if(u>n||v>n){ans++;continue;}

        if(opt==1)

            if(find(u+n)==find(v)||find(u)==find(v+n))ans++;

            else{

                fa[find(u)]=find(v);

                fa[find(u+n)]=find(v+n);

                fa[find(u+n+n)]=find(v+n+n);

            }

		else

            if(find(u)==find(v)||find(u)==find(v+n))ans++;

            else{

                fa[find(u+n)]=find(v);

                fa[find(u+n+n)]=find(v+n);

                fa[find(u)]=find(v+n+n);

            }

    }

	return cout<<ans,0;

}

完结撒花 \(qwq\)

巴特西

「NOI2001」食物链

解题思路

细节注意事项

参考代码

最新文章

热门文章