老铁们，大家好，相信还有很多朋友对于noipoj网站源码分享和源码网站推荐的相关问题不太懂，没关系，今天就由我来为大家分享分享noipoj网站源码分享以及源码网站推荐的问题，文章篇幅可能偏长，希望可以帮助到大家，下面一起来看看吧！
欢迎咨询报名NOIP2019冬令营！<-点击查看
并查集简介
并查集
并查集是一个很高效算法，理解起来也很简单，写起来更简单。
①fat[i]=i;
②找到一个点的祖先
intfindfat(intx){if(fat[x]==x)returnx;returnfindfat(fat[x]);}
③二中的方法肯定不好，因为如果数据比较极端，那么并查集就退化成一个链了
如果加入了路径压缩，并查集这个算法就更高效了。
intfindfat(intx)//递归写法{if(fat[x]==x)returnx;fat[x]=findfat(fat[x]);returnfindfat(fat[x]);}intfindfat(intx)//非递归写法更好，因为不会RE{introot=x;while(root!=fat[root])//先要找到根节点r{root=fat[root];}inty=x;while(y!=root){intfath=fat[y];fat[y]=root;y=fath;}returnr;}
④合并
voidjoin(intx,inty){intfatx=findfat(x),faty=findfat(y);if(fatx!=faty){fat[fatx]=faty;}}
带权并查集
带权值的并查集只不过是在并查集中加入了一个value[]数组
value[]可以记录很多种东西，不一定是类似距离这种东西，也可以是相对于根节点的状态
加入了权值，函数应该有一些改变
①找到一个点的祖先
intfindfat(intx){if(fat[x]==x)returnx;inttmp=fat[x];fat[x]=findfat(fat[x]);//在此处修改val比如：value[x]=value[tmp]+1;returnfat[x];}
以下题目标号来自HDU题库
并查集是一种维护不同集合，在此基础上实现快速判断，统计个数等等的算法。
基础的有find和join两个功能，其中join作用于接收新数据。
并查集应用场景的几个特点：
1.数据之间存在联系；
2.借由两个数据的联系，数据会被双向联通的结合成几个集合；
下面介绍下find和join的基本形式
constintmaxn=1000;
intp[maxn];//用于储存数据的根
voidinit(intn)
{
for(inti=0;i<n;i++)
{
p[i]=i;
}
}
intfind(intx)
{
intt=x;
while(p[t]!=t)t=p[t];
inti=x;
while(p[i]!=i)
{
inttem=p[i];
p[i]=t;
i=tem;
}
returnt;
}
这种是将关系优化避免出现树变成一条路
还有一种如下
intfind(intx)
{
if(p[x]==x)returnx;
inttem=find(p[x]);
returntem;
}
这种用递归的方法算
join函数：
voidjoin(intx,inty)
{
intf1=find(x),f2=find(y);
if(f1!=f2)
{
p[f1]=f2;
}
}
知道了这些，一些水题就可以做了
接着是在这个基础上的变化，如统计集合个数，一开始的想法是维护完数据后for一遍，实际这里可以发现，在p[]数组中，作为根节点的数据p[i]==i的，没有必要通过链表结构特点去找根节点。接着处理掉这个for循环：
再看看现在的思路，是通过遍历一遍p[]数组，统计满足p[i]==i的个数，假设为a。如果所有数据没有联通，那么集合个数为n，a=n-（原本p[i]==i的点的p[i]改变的次数），即在join函数中每次寻找到两个数据的根数据进行合并时加一个计数器，然后用n减去。可以这样实现：
intans=n;
voidjoin(intx,inty)
{
intf1=find(x),f2=find(y);
if(f1!=f2)
{
p[f1]=f2;
ans–;
}
}
接着是找集合中元素个数的题1856，这个可以通过增加一个初始化为1的数组，每次合并同时对应合并，同时max取最大值
include<string>
include<iomanip>
include<cmath>
include<vector>
include<functional>
pragmawarning(disable:4996)
usingnamespacestd;
//freopen(“john.in”,”r”,stdin);
//freopen(“john.out”,”w”,stdout);
intp[maxn];
intn[maxn];
voidpre()
{
for(inti=1;i<maxn;i++)
{
p[i]=i;
n[i]=1;
}
}
intfind(intx)
{
intr=x;
while(r!=p[r])
{
r=p[r];
}
inti=x;
while(i!=p[i])
{
intj=p[i];
p[i]=r;
i=j;
}
returnr;
}
voidjoin(intx,inty,int&ans)
{
inttem1=find(x),tem2=find(y);
if(tem1!=tem2)
{
p[tem1]=tem2;
n[tem2]+=n[tem1];
ans=max(n[y],ans);
}
}
intmain()
{
intt;
while(~scanf(“%d”,&t))
{
if(t==0)puts(“1”);
else
{
intans=0;
pre();
while(t–)
{
inti,j;
scanf(“%d%d”,&i,&j);
join(i,j,ans);
}
printf(“%d\\n”,ans);
}
}
}
还有一个应用是判断是否成环，如果join的两个数据p[]相同，则标记为成环，如1272这题，还要判断唯一性，可以用前面的方法，也可以通过图论中边数为定点数减一来判断
include<string>
include<iomanip>
include<cmath>
include<vector>
include<functional>
pragmawarning(disable:4996)
usingnamespacestd;
//freopen(“john.in”,”r”,stdin);
//freopen(“john.out”,”w”,stdout);
intp[maxn];
intflag;
bools[maxn];
intfind(inta)
{
while(a!=p[a])
{
a=p[a];
}
returna;
}
voidjoin(inta,intb)
{
inti=find(a),j=find(b);
if(i!=j)
{
p[i]=p[j];
}
elseflag=0;
}
voidpre()
{
for(inti=1;i<maxn;i++)
{
p[i]=i;
s[i]=false;
}
}
intmain()
{
inta,b;
while(cin>>a>>b)
{
if(a==-1&&b==-1)break;
if(a==0&&b==0)printf(“Yes\\n”);
else
{
flag=1;
pre();
s[a]=true;
s[b]=true;
join(a,b);
while(scanf(“%d%d”,&a,&b),(a||b))
{
s[a]=true;
s[b]=true;
join(a,b);
}
if(flag)
{
intcnt=0;
for(inti=1;i<maxn;i++)
{
if(s[i]&&p[i]==i)
{
cnt++;
}
if(cnt>1)
{
flag=0;
break;
}
}
}
if(flag)printf(“Yes\\n”);
elseprintf(“No\\n”);
}
}
}
然后是1198这题，这题没有显示的给出数据间的关系，需要对数据进行处理，但并查集的部分没有什么新东西
include<string>
include<iomanip>
include<cmath>
include<vector>
include<functional>
pragmawarning(disable:4996)
usingnamespacestd;
//freopen(“john.in”,”r”,stdin);
//freopen(“john.out”,”w”,stdout);
//上下左右分别为0123
intlist[11]={10,9,6,5,12,3,11,14,7,13,15};
chara[maxn][maxn];
intans;
intn,m;
intp[maxn*maxn+1];
voidpre(intn)
{
for(inti=0;i<n;i++)
{
p[i]=i;
}
}
intfind(intx)
{
intr=x;
while(r!=p[r])
{
r=p[r];
}
returnr;
}
voidjudge(intai,intaj,intbi,intbj)
{
if(bi>=m||bj>=n)return;
boolflag=false;
intt1=a[ai][aj]-‘A’;
intt2=a[bi][bj]-‘A’;
if(ai==bi&&aj<bj)
{
if(((list[t1])&1)&&((list[t2]>>1)&1))flag=true;
}
elseif(aj==bj&&ai<bi)
{
if(((list[t1]>>2)&1)&&((list[t2]>>3)&1))flag=true;
}
if(flag)
{
intf1=find(ai*n+aj),f2=find(bi*n+bj);
if(f1!=f2)
{
p[f1]=f2;
ans–;
}
}
}
intmain()
{
//freopen(“in.txt”,”r”,stdin);
while(scanf(“%d%d”,&m,&n)!=EOF)
{
if(m==-1||n==-1)break;
pre(m*n);
ans=n*m;
for(inti=0;i<m;i++)
{
scanf(“%s”,a[i]);
}
for(inti=0;i<m;i++)
{
for(intj=0;j<n;j++)
{
judge(i,j,i,j+1);
judge(i,j,i+1,j);
}
}
printf(“%d\\n”,ans);
}
}
然后是现在做的这题，关于带权并查集，还没有弄明白，1829，题意大概是选择动物，给出两个数据的性别相反，问是否出现前后矛盾的情况，上网看到一种解法，思路是开两个数组，每次接收数据，交换p[]中两个数据对应的值，如果有处理到两个数据的p[]相同，则错误。还有一种是带权并查集。做了一个晚上带权那种，还是有点没搞明白。
带权并查集多一个权值的数组，通过递归的find函数找到根节点。现在的问题是，每次找到根节点的过程和合并的过程，会让原本a->b->c的关系变成a->c,b->c每次更新后都要再次调整权值数组。网上的解释是把权值看成向量。例如sign[i]表示由i指向前一个节点的向量，那么改变后的指向由a->c，等于sign[a]+sign[p[a]]。
下面是代码：
include<string>
include<iomanip>
include<cmath>
include<vector>
include<functional>
pragmawarning(disable:4996)
usingnamespacestd;
//freopen(“john.in”,”r”,stdin);
//freopen(“john.out”,”w”,stdout);
constintmaxn=2002;
intp[maxn];
intsign[maxn];
intfind(intx)
{
if(p[x]==x){returnx;}
inttem=p[x];
p[x]=find(p[x]);
sign[x]=(sign[x]+sign[tem])%2;//用向量的思想来解释这个过程
returnp[x];
}
voidunit(intn)
{
for(inti=1;i<=n;i++)
{
p[i]=i;
sign[i]=0;
}
}
voidjoin(intx,inty)
{
intf1=find(x);
intf2=find(y);
if(f1!=f2)
{
p[f1]=f2;
sign[f1]=(1+sign[y]-sign[x])%2;
}
find(x);
}
intmain()
{
freopen(“in.txt”,”r”,stdin);
intt;
scanf(“%d”,&t);
intcnt=1;
while(t–)
{
intn,m;
scanf(“%d%d”,&n,&m);
unit(n);
boolflag=true;
while(m–)
{
inti,j;
scanf(“%d%d”,&i,&j);
if(flag)join(i,j);
if(sign[i]==sign[j])
{
flag=false;
}
}
printf(“Scenarioinclude<iostream>
include<cstdio>
include<cstring>
include<algorithm>
include<queue>
include<map>
#pragmawarning(disable:4996)
usingnamespacestd;
//freopen(“john.in”,”r”,stdin);
//freopen(“john.out”,”w”,stdout);
constintmaxn=50002;
intp[maxn];
intsign[maxn];
voidinit(intn)
{
for(inti=1;i<=n;i++)
{
p[i]=i;
sign[i]=0;
}
}
intfind(intx)
{
if(x==p[x])returnx;
inttem=p[x];
p[x]=find(p[x]);
sign[x]=(sign[x]+sign[tem])%3;
returnp[x];
}
booljoin(intx,inty,intd)
{
intf1=find(x),f2=find(y);
if(f1==f2)
{
if(d==1&&sign[x]!=sign[y])returnfalse;
if(d==2)
{
if(sign[x]==2&&sign[y]!=1)returnfalse;
if(sign[x]==0&&sign[y]!=2)returnfalse;
if(sign[x]==1&&sign[y]!=0)returnfalse;
}
returntrue;
}
p[f1]=f2;
if(d==1)
{
sign[f1]=(sign[y]-sign[x]+3)%3;
}
if(d==2)
{
sign[f1]=(sign[y]-sign[x]+1+3)%3;
}
find(x);//看看是否必要,可以ac，还是保留吧
returntrue;
}
intmain()
{
//freopen(“in.txt”,”r”,stdin);
intn,k;
scanf(“%d%d”,&n,&k);
init(n);
intans=0;
while(k–)
{
intd,x,y;
scanf(“%d%d%d”,&d,&x,&y);
if(x>n||y>n)
{
ans++;
continue;
}
if(x==y&&d==2)
{
ans++;
continue;
}
if(!join(x,y,d))ans++;//小心添加错的关系而对正确的关系造成破坏
//判断还是在函数中好，因为在这里会重复做过的事，找到find（x），（y）然后讨论sign[x]sign[y]的关系
}
printf(“%d\\n”,ans);
}
本文例题讲解部分作者roffen，原文链接https://www.cnblogs.com/roffen/p/6763328.html
欢迎咨询报名NOIP2019冬令营课程！<-点击查看详情
咨询方式：
司老师18610112920赵老师18610112915高老师18611056259老师18611083835张老师18610150289
定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的wx公众平台noipnoi
noipoj网站源码分享的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于源码网站推荐、noipoj网站源码分享的信息别忘了在本站进行查找哦。