最小生成树（基本）

最小生成树思路（基本）

链接两点

创建一个存储用的“树”

struct p{
  int x;int y;//连接的两个点
      int w;//连接用的价值（连接长度）
}

kruskal算法

排序条件

il bool cmp(p a,p b){
  //if(a.w==b.w)return a.x<b.x;//某些题可能会有特判
  return a.w<b.w;//按边的从小到大的顺序排列
}

排序（加权）（最短路）

sort(q+1,q+1+m,cmp);//排序

并查集 判断是否已入“树”

初始化

for(int i=0;i<=n;i++)fa[i]=i;

找祖先

il int f(int a){
  if(a!=fa[a])return a=fa[a]=f(fa[a]);//找爹
  return a;//返回祖先
}

入树

fa[z]=zz;

判终条件

不同题目，求的东西不同，判终条件不同

例如本题，要判的是两点之间的最短路，由于边是按照从小到大“入树”的，所以，只要判断是否都进“树”（祖先是否相同）即可。

if(f(s)==f(t))break;

例如 P2121 与本题思路相似但判终条件不同，此题要求的是拆地毯的数量，所以只要数量达到就可以结束

代码（例子）

#include<iostream>//标椎I/O
#include<cstdio>//scanf,printf 可缩短时间，但没有,cin,cout“智能”
#define il inline//用于缩短时间
using namespace std;
int n,m,s,t;
int fa[20001];//找爹
int sum=0;//判终止条件
int ss=0;//输出
struct p{
  int x;int y;
  int w; 
}q[20001];//“树”
il bool cmp(p a,p b){//排序
  if(a.w==b.w)return a.x<b.x;
  return a.w<b.w;
}
il int f(int a){//找祖先，判断是否以入“树”
  if(a!=fa[a])return a=fa[a]=f(fa[a]);
  return a;
}
int main(){
  cin>>n>>m>>s>>t;
  for(int i=1;i<=m;i++){
    cin>>q[i].x>>q[i].y>>q[i].w;//读入
  }
  for(int i=0;i<=n;i++)fa[i]=i;//初始化
  sort(q+1,q+1+m,cmp);//排序
  for(int i=1;i<=m;i++){
    int z=f(q[i].x),zz=f(q[i].y);//找祖先
    if(z!=zz){//若祖先相同，说明已经有更优的解（以入“树”）
      fa[z]=zz;//若还未入树，让它入树
      ss=q[i].w;//并更新值（因为排序是从小到大，所以后来的一定比先来的大，所以保证一直是最大值）
    }
    if(f(s)==f(t))break;//判终
  }
  cout<<ss;//输出
  return 0;//好习惯
}