那啥那啥 原本今天还是做（看）差分约束的，但是上不去Vjudge我只能来刷并查集了。
%%%静萱大佬把那么多年的noip题都刷遍了，我只能刷水题，noip的题实在是太难了不会啊。
第一道：洛谷P2024食物链
虽然说我很不喜欢看别人代码，但是我认为这道题看代码最容易懂：
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=5e4+10;
int n,m,ans,fa[3*maxn];
int aa;char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
}
int find(int x) {
return fa[x]==x? x:fa[x]=find(fa[x]);
}
int main() {
n=read();m=read();
for(int i=1;i<=3*n;++i) fa[i]=i;
int op,x,y,xx,yy;
for(int i=1;i<=m;++i) {
op=read();x=read();y=read();
if(x>n||y>n) {
ans++; continue;
}
if(op==1) {
if(find(x+n)==find(y)||find(x+2*n)==find(y)) {
ans++; continue;
}
xx=find(x);yy=find(y);
if(xx!=yy) fa[xx]=yy;
xx=find(x+n);yy=find(y+n);
if(xx!=yy) fa[xx]=yy;
xx=find(x+2*n);yy=find(y+2*n);
if(xx!=yy) fa[xx]=yy;
}
if(op==2) {
if(find(x)==find(y)||find(x+2*n)==find(y)) {
ans++; continue;
}
xx=find(x+n);yy=find(y);
if(xx!=yy) fa[xx]=yy;
xx=find(y+n*2);yy=find(x);
if(xx!=yy) fa[xx]=yy;
xx=find(x+n*2);yy=find(y+n);
if(xx!=yy) fa[xx]=yy;
}
}
printf("%d",ans);
return 0;
}
/*
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
*/
第二道：洛谷P3295萌萌哒
竟然用st表套并查集，感觉还是对st表不够了解啊。然后最后的时候像线段树一样下放。。。父子关系？
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
const int maxn=2e5+10;
const ll mod=1e9+7;
int n,m,ql,qr,fl,fr,sz,ans;
int fa[maxn][25];
bool ok[maxn];
int aa; char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
}
int find(int x,int y) {
return fa[x][y]==x? x : fa[x][y]=find(fa[x][y],y);
}
ll qp(ll x,ll k) {
ll rs=1;
while(k) {
if(k&1) (rs*=x)%=mod;
k>>=1; x=x*x%mod;
}
return rs;
}
int main() {
n=read();m=read(); int c,t,xx,yy;
for(int i=1;i<=n;++i) for(int j=0;(1<<j)<=n;++j) fa[i][j]=i;
for(int i=1;i<=m;++i) {
ql=read();qr=read();
fl=read();fr=read();
if(ql==fl) continue;
c=qr-ql+1; for(t=0;(1<<t)<=c;++t) ; t--; sz=max(sz,t);
xx=find(ql,t); yy=find(fl,t);
if(xx!=yy) fa[xx][t]=yy;
xx=find(qr-(1<<t)+1,t); yy=find(fr-(1<<t)+1,t);
if(xx!=yy) fa[xx][t]=yy;
}
for(int j=sz;j;--j) for(int i=1;i<=n;++i) {
xx=find(i,j-1);yy=find(find(fa[i][j],j),j-1);
if(xx!=yy) fa[xx][j-1]=yy;
xx=find(i+(1<<j-1),j-1);yy=find(find(fa[i][j],j)+(1<<j-1),j-1);
if(xx!=yy&&yy<=n) fa[xx][j-1]=yy;
}
for(int i=1;i<=n;++i) if(!ok[xx=find(i,0)]) {
ans++; ok[xx]=1;
}
printf("%lld",qp(10,ans-1)*9%mod);
return 0;
}
/*
10 7
2 4 6 8
1 3 7 9
2 2 3 3
1 1 1 1
1 7 2 8
6 7 8 9
1 9 2 10
*/
第三道：洛谷P1955程序自动分析
这种题就是应该乱搞！
先处理=的情况，然后判不等于是否成立就可以了。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
const int maxn=2e5+10;
int T,n,d[maxn],tot=0,fa[maxn];
bool ok;
set<int> G;
set<int>::iterator it;
int aa; char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
}
struct Node{
int x,y,e;
}node[maxn];
bool cmp(const Node& a,const Node& b) {
return a.e>b.e;
}
int find(int x) {
return x==fa[x]? x:fa[x]=find(fa[x]);
}
int ef(int x) {
int l=0,r=tot,mid;
while(l<r-1) {
mid=(l+r)>>1;
if(d[mid]==x) return mid;
if(d[mid]<x) l=mid;
else r=mid-1;
}
return r;
}
int main() {
T=read();
while(T--) {
n=read(); G.clear(); tot=0;
int x,y,p,xx,yy; ok=0;
for(int i=1;i<=n;++i) {
node[i].x=read();
node[i].y=read();
node[i].e=read();
G.insert(node[i].x);
G.insert(node[i].y);
}
sort(node+1,node+n+1,cmp);
for(it=G.begin();it!=G.end();++it) d[++tot]=*it;
for(int i=1;i<=tot;++i) fa[i]=i;
for(int i=1;i<=n;++i) {
x=ef(node[i].x); y=ef(node[i].y); p=node[i].e;
xx=find(x);yy=find(y);
if(p&&xx!=yy) fa[xx]=yy;
if(!p&&xx==yy) ok=1;
}
if(ok) printf("NO
");
else printf("YES
");
}
return 0;
}
第四道：P1196银河英雄传说
这个就是并查集是有向的不能乱搞。然后维护一个$x$到$fa[x]$的距离$len$和对于每一个代表员所管辖的节点个数$end$。在find的时候也要更新一下。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=30000+10;
int n,len[maxn],end[maxn],fa[maxn];
int aa; char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
}
int find(int x) {
if(x==fa[x]) return x;
int y=fa[x];
fa[x]=find(fa[x]);
len[x]+=len[y];
return fa[x];
}
int main() {
n=read(); char c; int x,y,xx,yy;
for(int i=1;i<=30000;++i)len[i]=0,end[i]=1,fa[i]=i;
for(int i=1;i<=n;++i) {
do c=getchar();while(c!='M'&&c!='C');
x=read();y=read();
xx=find(x);yy=find(y);
if(c=='M') {
fa[xx]=yy; len[xx]+=end[yy]; end[yy]+=end[xx];
}
else {
if(xx==yy) printf("%d
",abs(len[x]-len[y])-1);
else printf("-1
");
}
}
return 0;
}
第五道：洛谷P1195口袋的天空
像最小生成树一样搞。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1000+10,maxm=10000+10;
int n,m,k,fa[maxn],now,ans;
int aa; char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
}
struct Edge{
int x,y,l;
}edge[maxm];
bool cmp(const Edge& a,const Edge& b) {
return a.l<b.l;
}
int find(int x) {
return fa[x]==x? x:fa[x]=find(fa[x]);
}
int main() {
n=read();m=read(); k=read(); now=n;
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i) {
edge[i].x=read();
edge[i].y=read();
edge[i].l=read();
}
sort(edge+1,edge+m+1,cmp);
int xx,yy;
for(int i=1;i<=m&&now>k;++i) {
xx=find(edge[i].x);yy=find(edge[i].y);
if(xx!=yy) {
fa[xx]=yy; ans+=edge[i].l; now--;
}
}
if(now!=k) printf("No Answer");
else printf("%d",ans);
return 0;
}