T1.relation(亲戚)
题意：给定一些人是亲戚的关系，并询问某两人是不是亲戚
分析：利用并查集维护每个亲戚集合。
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 5001
using namespace std;
int fa[MX];
int n,m,p;
int findfa(int x){return fa[x]==x?x:(fa[x]=findfa(fa[x]));}
void comb(int a,int b){fa[findfa(a)]=findfa(b);}
int main()
{
freopen("relation.in","r",stdin);
freopen("relation.out","w",stdout);
int a,b;
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
comb(a,b);
}
for(int i=1;i<=p;i++)
{
scanf("%d%d",&a,&b);
if(findfa(a)==findfa(b))printf("Yes\n");
else printf("No\n");
}
return 0;
}
T2.gangs(黑社会团伙)
题意：我的朋友的朋友是我的朋友，我的敌人的敌人是我的朋友。现在给出一些人的关系，求最多存在多少组朋友 (单独的人也是一组朋友)
思路：这道题有多种理解，按照 “朋友的敌人是敌人，敌人的朋友也是敌人” 的理解，我们可以用带权并查集做。
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 5001
using namespace std;
int fa[MX],dis[MX];
int kind[MX];
int n,m;
int findfa(int x)
{
if(fa[x]==x)return x;
else
{
findfa(fa[x]);
dis[x]+=dis[fa[x]];
fa[x]=fa[fa[x]];
return fa[x];
}
}
void frid(int a,int b)
{
int f1,f2;
f1=findfa(a),f2=findfa(b);
if(f1==f2)return;
fa[f1]=f2;
if(dis[a]%2==dis[b]%2)dis[f1]=0;
else dis[f1]=1;
}
void enem(int a,int b)
{
int f1,f2;
f1=findfa(a),f2=findfa(b);
if(f1==f2)return;
fa[f1]=f2;
if(dis[a]%2!=dis[b]%2)dis[f1]=0;
else dis[f1]=1;
}
int main()
{
freopen("gangs.in","r",stdin);
freopen("gangs.out","w",stdout);
char op;
int a,b;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
op=getchar();
while(op!='E'&&op!='F')op=getchar();
scanf("%d%d",&a,&b);
if(op=='E')enem(a,b);
else frid(a,b);
}
for(int i=1;i<=n;i++)
{
findfa(i);
if(kind[fa[i]]==0&&dis[i]%2==0)kind[fa[i]]++;
if(kind[fa[i]]==1&&dis[i]%2==1)kind[fa[i]]++;
}
for(int i=1;i<=n;i++)
{
if(kind[fa[i]]==0&&dis[i]%2==0)kind[fa[i]]++;
if(kind[fa[i]]==1&&dis[i]%2==1)kind[fa[i]]++;
}
int tot=0;
for(int i=1;i<=n;i++)tot+=kind[i];
printf("%d\n",tot);
return 0;
}
T3.filling(矩形填补)
题意：平面上的边平行于坐标轴的矩形，如果三个角上有黑点，那么将第四个角也染成黑点。现在给出一开始的黑点，求最后平面上有多少个点。
分析：注意到最后形成的点集一定为几个互相没有公共点的矩形的并 (这里的矩形包括 33,34 等的内部有多个点的矩形)。为什么会这样呢？把每个点所在的横线和竖线画出来自然就清楚了。经过分析，我们得出以下结论：
1. 一个点可以将它所在的横线和竖线连接起来。
2. 两个已经被连接起来的线的交点一定是一个黑点。
所以我们只需要维护有多少横线竖线被点连接在一起。这个利用并查集可以轻松完成。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 1000010
using namespace std;
typedef struct sfga
{
int x,y;
int sx,sy;
}point;
int fa[MX],mx,my;
int ynum[MX],xnum[MX];
char vis[MX];
point src[MX/2];
int n;
int cmpx(point a,point b){if(a.x==b.x)return a.y<b.y;else return a.x<b.x;}
int cmpy(point a,point b){if(a.y==b.y)return a.x<b.x;else return a.y<b.y;}
int findfa(int x){return x==fa[x]?x:(fa[x]=findfa(fa[x]));}
void comb(int a,int b)
{
if(findfa(a)==findfa(b))return;
xnum[findfa(b)]+=xnum[findfa(a)];
ynum[findfa(b)]+=ynum[findfa(a)];
fa[findfa(a)]=findfa(b);
}
int main()
{
freopen("filling.in","r",stdin);
freopen("filling.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&src[i].x,&src[i].y);
sort(src+1,src+n+1,cmpx);
for(int now=0,i=1;i<=n;i++)
{
if(src[i].x!=src[i-1].x||i==1)now++;
src[i].sx=now;
mx=now;
}
sort(src+1,src+n+1,cmpy);
for(int now=0,i=1;i<=n;i++)
{
if(src[i].y!=src[i-1].y||i==1)now++;
src[i].sy=now;
my=now;
}
for(int i=1;i<=mx+my;i++)fa[i]=i;
for(int i=1;i<=mx;i++)xnum[i]=1;
for(int i=mx+1;i<=mx+my;i++)ynum[i]=1;
for(int i=1;i<=n;i++)comb(src[i].sx,src[i].sy+mx);
long long ans=0;
for(int i=1;i<=mx+my;i++)
{
if(vis[findfa(i)])continue;
ans+=(long long)xnum[fa[i]]*(long long)ynum[fa[i]];
vis[fa[i]]=1;
}
cout<<ans<<endl;
return 0;
}
T4.game(格子游戏)
题意：两位大爷在 n*n 的棋盘上连线，两人轮流连接一条棋盘上的单位长度的边，给出每一步他们连接的起始点坐标和连接方向，求谁先连出一个环。
分析：并查集维护连通性。
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 2000010
using namespace std;
int fa[MX],n,m;
int findfa(int x){return (x==fa[x]?x:(fa[x]=findfa(fa[x])));}
int comb(int a,int b)
{
if(findfa(a)==findfa(b))return 1;
fa[findfa(a)]=findfa(b);
return 0;
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int x,y;
char c;
scanf("%d%d",&n,&m);
for(int i=1;i<=n*(n+1);i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
c=getchar();
while(c!='D'&&c!='R')c=getchar();
if(c=='D')
{
if(comb((x-1)*(n+1)+y,x*(n+1)+y))
{
cout<<i<<endl;
return 0;
}
}
else
{
if(comb((x-1)*(n+1)+y,(x-1)*(n+1)+y+1))
{
cout<<i<<endl;
return 0;
}
}
}
cout<<-1<<endl;
return 0;
}
T5.lyp(打怪兽)
题意：有 n 个怪兽，不停给出如下两个操作：
1 a b c: 告诉你 a 怪兽比 b 怪兽强 c
2 a b：询问 a 和 b 谁强。如果一样强或不知道，就输出 0
分析：带权并查集维护每个怪兽比所在根节点的怪兽强多少。
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 31000
using namespace std;
int fa[MX],dis[MX];
int n,q;
int findfa(int x)
{
if(fa[x]==x)return x;
else
{
findfa(fa[x]);
dis[x]+=dis[fa[x]];
fa[x]=fa[fa[x]];
return fa[x];
}
}
void big(int a,int b,int c)
{
int f1=findfa(a),f2=findfa(b);
if(f1==f2)return;
fa[f1]=f2;
dis[f1]=dis[b]-dis[a]+c;
}
int query(int a,int b)
{
int f1=findfa(a),f2=findfa(b);
if(f1!=f2)return 0;
if(dis[a]==dis[b])return 0;
return (dis[a]>dis[b]?a:b);
}
int main()
{
freopen("lyp.in","r",stdin);
freopen("lyp.out","w",stdout);
int op,a,b,c;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=q;i++)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&a,&b,&c);
big(a,b,c);
}
else
{
scanf("%d%d",&a,&b);
printf("%d\n",query(a,b));
}
}
return 0;
}
0 条评论