并查集&最小生成树题解
A
解题思路: 计算几个连通块，并查集一下即可
B
解题思路: 计算这片连通森林还需要几条边变成一个连通块，那么需要数量就是连通块数量减去$1$
C
解题思路: 最小生成树模板题
D
解题思路: $MST$模板题，先加上已经选择的边，再加上没有选择的边即可
E
解题思路: 判断是否只有一个$MST$，那么我们可以先找到一棵$MST$，记录这一棵$MST$的边，然后我们暴力去枚举去掉这条边之后是否还存在一棵和之前权值一样的$MST$
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
struct node
{
int x,y,r;
}a[maxn];
int flag[maxn],n,m;
struct DSU
{
int f[maxn],num;
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
int merge(int x,int y)
{
int fx = getf(x);
int fy = getf(y);
f[fx] = fy;
if(fx != fy)
{
num++;
return 1;
}
else return 0;
}
void init()
{
for(int i = 1;i <= n;++i) f[i] = i;
num = 0;
}
}dsu;
struct kruskal
{
DSU now;
int nowres;
void init()
{
now.init();
nowres = 0;
}
}kru;
int cmp(node A,node B)
{
return A.r < B.r;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n >> m;
dsu.init();
for(int i = 1;i <= m;++i)
{
cin >> a[i].x >> a[i].y >> a[i].r;
flag[i] = 0;
}
sort(a + 1,a + 1 + m,cmp);
int ans = 0;
for(int i = 1;i <= m;++i)
{
if(dsu.merge(a[i].x,a[i].y))
{
ans += a[i].r;
flag[i] = 1;
}
}
int f = 1;
for(int i = 1;i <= m;++i)
{
if(!flag[i]) continue;
kru.init();
for(int j = 1;j <= m;++j)
{
if(j == i) continue;
if(kru.now.merge(a[j].x,a[j].y))
{
kru.nowres += a[j].r;
}
}
if(kru.nowres == ans && kru.now.num == n - 1) f = 0;
}
if(f) cout << ans << "\n";
else cout << "Not Unique!\n";
}
}
F
解题思路: 首先先把免费的边连接起来，然后对$n$个点建立点对，排序之后求最小生成树，直接用$Kruskal$记录边即可
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
const int maxn = 1e6 + 10;
int p[maxn][2],tot,n,m;
struct node
{
int x,y;
double r;
node(){};
node(int _x,int _y,double _r): x(_x),y(_y),r(_r){}
}a[maxn];
struct DSU
{
int f[maxn];
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
void merge(int x,int y,int op)
{
int fx = getf(x);
int fy = getf(y);
if(fx != fy)
{
f[fx] = fy;
if(op) cout << x << " " << y << "\n";
}
}
void init()
{
for(int i = 1;i <= n;++i) f[i] = i;
}
}dsu;
int pow2(int x)
{
return x * x;
}
double cal(int i,int j)
{
return sqrt(1.0 * pow2(p[i][0] - p[j][0]) + 1.0 * pow2(p[i][1] - p[j][1]));
}
int cmp(node A,node B)
{
return A.r < B.r;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1;i <= n;++i)
{
cin >> p[i][0] >> p[i][1];
}
cin >> m;
dsu.init();
for(int i = 1,u,v;i <= m;++i)
{
cin >> u >> v;
dsu.merge(u,v,0);
}
for(int i = 1;i <= n;++i)
{
for(int j = i + 1;j <= n;++j)
{
double dis = cal(i,j);
a[++tot] = node(i,j,dis);
}
}
sort(a + 1,a + 1 + tot,cmp);
for(int i = 1;i <= tot;++i)
{
dsu.merge(a[i].x,a[i].y,1);
}
return 0;
}G
解题思路: 和上课讲的基本类似，同时需要注意的是这里存在位置固定的问题，如果位置固定的话那么对于他所存在的连通块只会带来$1$的贡献
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;
int a[maxn],b[maxn],c[maxn],n;
struct DSU
{
int f[maxn],sz[maxn];
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
void merge(int x,int y)
{
int fx = getf(x);
int fy = getf(y);
if(fx != fy)
{
f[fy] = fx;
sz[fx] += sz[fy];
}
}
void init()
{
for(int i = 1;i <= n;++i) f[i] = i,sz[i] = 1;
}
}dsu;
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1;i <= n;++i) cin >> a[i];
for(int i = 1;i <= n;++i) cin >> b[i];
for(int i = 1;i <= n;++i) cin >> c[i];
dsu.init();
for(int i = 1;i <= n;++i)
{
dsu.merge(a[i],b[i]);
}
for(int i = 1;i <= n;++i)
{
if(c[i])
{
dsu.sz[dsu.getf(c[i])] = 0;
}
}
int ans = 1;
for(int i = 1;i <= n;++i)
{
if(dsu.f[i] == i)
{
if(dsu.sz[i] >= 2) ans = ans * 2 % mod;
}
}
cout << ans << "\n";
}
}
H
解题思路: 种族并查集，首先我们先思考如何解决多个种族之间的事情，首先我们先考虑$A$这个位置，因为它可以吃$B$,但是被$C$吃，因此在这里的关系存在的是三种：自己(同族)，食物，敌人。所以我们再开空间的时候可以开$3$倍的空间。
然后我们考虑这样一件事情，假设$a$可以吃$b,c$，那么$b,c$实际上是同族；同理如果$b,c$可以吃$a$，那么$b,c$也是同族。那么也就是说 敌人的敌人是朋友
那么接下来考虑什么时候不合法，首先是在$x$和$y$合并的时候，如果$x$是$y$的敌人或者$y$是$x$的敌人就不行
然后考虑$x$可以吃$y$的情况下，首先是题目告诉如果相同就不行，然后是如果$x$是$y$的同族或者$y$可以吃$x$不行
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
// const int inf = 1e18;
int f[maxn * 3],n,m,ans;
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
void merge(int x,int y)
{
int fx = getf(x);
int fy = getf(y);
f[fx] = fy;
}
signed main()
{
// ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// cin >> n >> m;
scanf("%d %d",&n,&m);
for(int i = 1;i <= 3 * n;++i) f[i] = i;
//A -> B -> C -> A
for(int i = 1,op,x,y;i <= m;++i)
{
scanf("%d %d %d",&op,&x,&y);
if(x > n || y > n)
{
ans++;
continue;
}
if(op == 1)
{
if(getf(x) == getf(y + 2 * n) || getf(x + 2 * n) == getf(y))
{
ans++;
}
else
{
merge(x,y);
merge(x + n,y + n);
merge(x + 2 * n,y + 2 * n);
}
}
else
{
if(x == y)
{
ans++;
}
else if(getf(x) == getf(y) || getf(x + 2 * n) == getf(y))
{
ans++;
}
else
{
merge(x,y + 2 * n);
merge(x + n,y);
merge(x + 2 * n,y + n);
}
}
}
printf("%d\n",ans);
return 0;
}I
解题思路: 求一个连通块最大是多少，但是由于标号很大所以我们先需要离散化再进行并查集查找即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int ans,n;
struct DSU
{
unordered_map<int,int> f;
unordered_map<int,int> sz;
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
void merge(int x,int y)
{
int fx = getf(x);
int fy = getf(y);
if(fx != fy)
{
f[fx] = fy;
sz[fy] += sz[fx];
ans = max(ans,sz[fy]);
}
}
void init()
{
f.clear();
sz.clear();
ans = 0;
}
}dsu;
array<int,2> p[maxn];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
dsu.init();
cin >> n;
for(int i = 1,u,v;i <= n;++i)
{
cin >> u >> v;
p[i] = {u,v};
dsu.f[u] = u,dsu.sz[u] = 1;
dsu.f[v] = v,dsu.sz[v] = 1;
}
for(int i = 1;i <= n;++i)
{
auto [u,v] = p[i];
dsu.merge(u,v);
}
cout << ans << "\n";
}
return 0;
}J
题目大意: 有三个长度为$n$的序列$a,b,c$
$Alice$和$Bob$玩游戏，一共进行$n$个回合，游戏规则如下：
- 选定$a_i,b_i,c_i$
- $Alice$从这三个数字选择一个数字删掉
- $Bob$从这三个数字选择一个数字
我们让$Bob$每回合选择的数字是$d_i$,如果序列$d$是一个排列那么$Alice$获胜否则$Bob$获胜
现在给定$a,b$两个数组，问有多少个$c$数组可以使得$Bob$获胜，结果对$998244353$取模
解题思路: 首先我们先考虑$Alice$会选择什么数字删掉，假设对于第$i$次操作来说，$a_i = b_i$,那么我们可以选择任意的$c_i$并且最终把$c_i$删掉，这样子$Bob$一定取到的是$a_i$这个数字表示的值(因为$a_i = b_i$)
然后我们考虑如果$a_i \neq b_i$那么我们选择的$c_i$就非常重要，因为$c_i$决定着我们可以选择$a_i$或者$b_i$中的哪个数字，只需要让$c_i = a_i \ or \ c_i = b_i$即可
那么选择某一个位置的思路就很清晰了，我们只需要考虑构造大于等于两个相同的并且把其中一个不需要的值删掉即可
接下来我们再考虑位置之间带来的因素
假设我们没有$a_i = b_i$的情况，那么我们现在的问题可以转换为给定两个序列分别是$a,b$，每个位置上面取一个看是否可以构成一个排序
对于这一个问题来说，因为每一个位置做一个选择，同时也相同与每一个位置的两个数字相互制衡，那么我们可以用图论的语言来表达，在他们之间建一条边
我们可以发现只有基环树的形式是可以的，而基环树的形式实际上就是点数等于边数
那么我们最终只需要使用并查集取维护每个环中存在点数和边数即可
那么最后再思考答案贡献，对于一个基环树来说，如果这个树里面没有自环，那么贡献就是$2$，因为考虑每条边有两个选择，如果里面有自环的话，贡献就是$n$
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
const int maxn = 1e6 + 10;
const int mod = 998244353;
int n,m,a[maxn],b[maxn];
int f[maxn],szv[maxn],sze[maxn],loop[maxn];
void init()
{
for(int i = 1;i <= n;++i)
{
f[i] = i;
szv[i] = 1;
sze[i] = 0;
loop[i] = 0;
}
}
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
void merge(int x,int y)
{
int fx = getf(x);
int fy = getf(y);
if(fx != fy)
{
f[fy] = fx;
sze[fx] += sze[fy];
szv[fx] += szv[fy];
loop[fx] += loop[fy];
}
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
init();
for(int i = 1;i <= n;++i) cin >> a[i];
for(int i = 1;i <= n;++i) cin >> b[i];
for(int i = 1;i <= n;++i)
{
merge(a[i],b[i]);
sze[getf(a[i])]++;
if(a[i] == b[i]) loop[getf(a[i])]++;
}
int ans = 1;
for(int i = 1;i <= n;++i)
{
if(i == getf(i))
{
if(sze[i] != szv[i]) ans = 0;
else ans = ans * 2 % mod;
}
}
cout << ans << "\n";
}
return 0;
}
