图论模版
2026-08-17 21:02:28
发布于：广东
3阅读
0回复
0点赞
并查集
int find(int x){
if(fa[x]!=x) return fa[x]=find(fa[x]);//fa[i]表示点i祖先
return x;
}
for(int i=1;i<=n;i++) fa[i]=i;//最开始自己是自己的祖先
while(m--){
cin>>op>>x>>y;
int fx=find(x),fy=find(y);
if(op==1){//添加元素
if(fx!=fy) fa[fx]=fy;//假设fx输,成为fx的孩子(假设fx赢同理)
}
else{//判断是否在同一个集合
if(fa[x]==fa[y]) cout<<"Y\n";
else cout<<"N\n";
}
}
Kruscal算法
int find(int x){
if(fa[x]!=x) return fa[x]=find(fa[x]);
return x;
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
int cnt=n,ans;//目前有n个连通块
for(int i=1;i<=m;i++){
int x=a[i].x,y=a[i].y,z=a[i].z;
if(cnt==1) break;//生成完毕,只有一个连通块
if(find(x)!=find(y)){//若两条边不在一个并查集里,合并
fa[find(x)]=find(y);
ans+=z;
cnt--;//少了一个点(被加入最小生成树中)
}
}
Dijkstra算法
struct node{
int v,w;
bool operator<(const node& other) const{//重载运算符
return w>other.w;
}
};
for(int i=1;i<=n;i++) d[i]=1e18;
priority_queue<node> q;
d[s]=0;
q.push({s,0});
while(q.size()){
node f=q.top();
q.pop();
if(vis[f.v]) continue;
vis[f.v]=1;
for(auto V:g[f.v]){//遍历进行松弛操作
int v=V.v,w=V.w;
if(d[v]>d[f.v]+w){
d[v]=d[f.v]+w;
q.push({v,d[v]});
}
}
}
Bellman-Ford算法
void bellman_ford(){
for(int i=1;i<=n;i++) dis[i]=1e18;
dis[1]=0;
for(int i=0;i<n;i++){
for(int j=1;j<=n;j++) ls[j]=dis[j];//记录上一次的值
for(int j=1;j<=m;j++){//枚举m条边
node e=edge[j];
if(ls[e.x]<1e18) dis[e.y]=min(dis[e.y],ls[e.x]+e.z);
}
}
}
Floyd算法
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) dp[i][j]=0;
else dp[i][j]=1e18;
}
}
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
dp[u][v]=min(w,dp[u][v]);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dp[i][k]!=1e18&&dp[k][j]!=1e18) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
这里空空如也
有帮助，赞一个