《不能使用最小生成树的情况》

在没有说不能产生回路时：

 这个情况是不能使用最小生成树算法的，因为边可以是负的，如果再加上一条边，这条边是负的，正好还可以减少权重

《Kruskal算法的大用》

用kruskal算法就像用一个进度条求最小生成树一样，即如果在开始时，最小生成树已经完成了一部分，可以用

kruskal算法继续完成，或者有些必要条件必须选边用这个算法更加方便，如：

 连接格点这道题，如果像平常使用kruskal算法包含sort会超时，

那我们可以在建图的时候就按照边权小的先建

 1 #include<bits/stdc++.h>
 2 #define N 1010
 3 using namespace std;
 4 int n,m;
 5 int fa[N*N],tot;
 6 int find(int x)//并查集基本操作
 7 {
 8     if(fa[x]==x)
 9         return x;
10     return fa[x]=find(fa[x]);
11 }
12 inline int merge(int x,int y)//并查集基本操作
13 {
14     int fa_x=find(x);
15     int fa_y=find(y);
16     if(fa_x!=fa_y){
17         fa[fa_y]=fa_x;
18         return 1;//已经连了一条边
19     }
20     return 0;
21 }
22 int main()
23 {
24     scanf("%d %d",&n,&m);
25     for(int i=1;i<=n*m;i++)//并查集初始化
26        fa[i]=i;
27     int x1,y1,x2,y2;
28     while(~scanf("%d %d %d %d",&x1,&y1,&x2,&y2)){
29         int u=(x1-1)*m+y1,v=(x2-1)*m+y2;//转换为对应的编号
30         merge(u,v);//合并
31     }
32     for(int i=1;i<=m;i++)//竖向合并一遍
33         for(int j=1;j<n;j++){
34             int u=(j-1)*m+i,v=j*m+i;//坐标转换
35             if(merge(u,v))//当前两点有一条边连接
36                 tot++;//竖向答案+1
37         }
38     for(int i=1;i<=n;i++)//横向合并一遍
39         for(int j=1;j<m;j++){
40             int u=(i-1)*m+j,v=(i-1)*m+j+1;//坐标转换
41             if(merge(u,v))//当前两点有一条边连接
42                 tot+=2;//横向答案+2
43         }
44     printf("%d\n",tot);
45     return 0;
46 }