XP04-02 DAY05
2025-08-06 18:33:18
发布于：上海
7阅读
0回复
0点赞
今天主要学习了提高组复赛知识点：并查集和相关的最小生成树。复习了最短路的一些相关算法。
一.并查集和最小生成树
并查集，最喜欢找爹的一集。
也就是查找最近公共祖先的算法。
也就是在图论中找父亲节点。
但是仔细想想，一个一个节点的遍历过去时间复杂度太高了，所以就有了所谓“路径压缩”。
听起来很诡异，但其实做法非常简单。
看图：链接描述
所谓路径压缩，就是在查找祖先节点的过程中，将自己的父节点转换为父节点的父节点的父节点的.....
这个查找的过程是递归，递归要有截止条件，其截止条件就是当前的节点，它没有父节点/父节点就是自己（根据初始化不同而不同）。
模版代码：
#include<bits/stdc++.h>
using namespace std;
int zu[200005];
int c(int x){
return (x==zu[x])?x:zu[x]=c(zu[x]);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)zu[i]=i;
for(int i=1;i<=m;i++){
int z,x,y;
cin>>z>>x>>y;
if(z==1){
zu[c(x)]=zu[c(y)];
}else{
if(c(x)==c(y))cout<<"Y"<<'\n';
else cout<<"N"<<'\n';
}
}
return 0;
}
与其相关的还有最小生成树，那个在此不进行解释（没时间了，还要默模版）
最小生成树模版：链接描述
#include<bits/stdc++.h>
using namespace std;
int z[100005];
int sz[1000005];
struct Node{
int x,y,z;
}node[200005];
bool cmp(Node a,Node b){
return a.z<b.z;
}
int c(int xx){
return (xx==z[xx])?xx:z[xx]=c(z[xx]);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)z[i]=i,sz[i]=1;
for(int i=1;i<=m;i++){
cin>>node[i].x>>node[i].y>>node[i].z;
}
sort(node+1,node+1+m,cmp);
long long ans=0;
for(int i=1;i<=m;i++){
if(z[c(node[i].x)]==z[c(node[i].y)])continue;
sz[c(node[i].y)]+=sz[c(node[i].x)];
z[c(node[i].x)]=c(node[i].y);
ans+=node[i].z;
}
if(sz[c(1)]==n)cout<<ans;
else cout<<"orz";
return 0;
}
二.最短路问题
Dijkstra
对于这个算法不多进行解释，详情请见坐着的其他文章。
模版：链接描述
#include<bits/stdc++.h>
using namespace std;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v[2000006];
long long dis[2000006];
bool vis[2000006];
priority_queue<Node>pq;
int main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({y,z});
}
for(int i=0;i<=n+1;i++)dis[i]=1e18;
dis[s]=0;
pq.push({s,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
pq.push({to,dis[to]});
}
}
}
for(int i=1;i<=n;i++){
if(dis[i]==1e18)dis[i]=-1;
cout<<dis[i]<<" ";
}
return 0;
}
SPFA
模版：链接描述
#include<bits/stdc++.h>
using namespace std;
struct Node{
int z,q;
};
vector<Node>v[1005];
bool vis[1005];
long long dis[1005];
queue<int>q;
int cnt[1005];
int main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({y,z});
}
for(int i=0;i<=n+1;i++)dis[i]=1e18;
vis[s]=1;
dis[s]=0;
q.push(s);
while(!q.empty()){
int k=q.front();
q.pop();
vis[k]=0;
cnt[k]++;
if(cnt[k]>=n){
cout<<"no solution";
return 0;
}
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
long long len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to]){
vis[to]=1;
q.push(to);
}
}
}
}
for(int i=1;i<=n;i++){
if(dis[i]==1e18)dis[i]=-1;
cout<<dis[i]<<" ";
}
return 0;
}
FLOYD(阴间版）
模版：链接描述
#include<bits/stdc++.h>
using namespace std;
long long a[1005][1005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=1e18;
}
}
for(int i=0;i<=n;i++)a[i][i]=0;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
long long z;
cin>>z;
a[x][y]=min(a[x][y],z);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][k]!=1e18&&a[k][j]!=1e18){
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
}
}
for(int i=1;i<=n;i++){
if(a[i][i]<0){
cout<<-1;
return 0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]==1e18)a[i][j]=1e9;
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个