题解 P1195 【口袋的天空】

· · 题解

这个题思路倒是很简单：最小生成树嘛~

最小生成树是个啥？其实就像杨志一行人押送生辰纲。抛开最后生辰纲被抢的结局不谈，杨志他们需要到好几个地方，每个地方都需要花点过路费给梁山好汉们打点。比如下面就是一张城市地图：

其中每两个图之间的路径长就是要给梁山好汉们打点的银子数。比如1号地点到2号地点的梁山好汉需要2两银子。那么问题来了，怎样才能选择其中一部分道路就可以到达所有地点且让总花费值最小呢？？？

如果有n个节点（城市），那就至少要连（n-1）条边（路线），并且肯定没有回路。（不信？画几个图试试）众所周知，在无向图中，只要这个图里没有回路（有（n-1）条边），那它就无疑是棵树了。（还是不信？画图......）所以，我们就管这棵各边权值（费用）和叫“最小生成树”了。

那这个最小生成树到底怎么搞呢？我们伟大的先哲发明了两种算法：一种叫Kruskal算法，另一种叫Prim算法。我们这里就来介绍一下名字字典序靠前的那个Kruskal吧！（我才不会告诉你根本原因是本蒟蒻不会用Prim呢！）

那咱就开始吧！首先，我们读入的数据是这样的！

1 2 2
1 3 2
1 4 4
2 3 3
3 4 4

其中每一行的a,b,c 3个数是指a到b的路径权值是c哦！

既然题目中让我们求“最小”生成树，那咱们就自然而然地想到先把这些边排个序，先用最小的边，从小到大一路把这棵树搞出来！

说干就干，排一个呗！

1 2 2
1 3 2 
2 3 3
1 4 4
3 4 4

排好之后，映入我们眼帘的是“1，2，2”这条边，二话不说，把它放到生成树里！

接下来是“1，2，2”，很好，把它也加进去

然后是“2，3，3”，好多同学把它都加了进去......

等会等会，先别忙着加！好像有什么猫腻！前面说过，最小生成树，是不能带回路的，加进去一不是最小，二它连个树都不是，所以不能加！于是我们意识到：在每次加进去新边之前，一定要看看它和其它边会不会构成回路才行！

那咱就只能退而求其次，选其它的边啦，“1，4，4”这可不是回路，没问题！

至此，边数已达（n-1）条，所有点已经选上，最小生成树大功告成！（当然，选下面的“3，4，4”也是阔以的）

总结一下，我们刚才是怎样搞出这棵最小生成树的：

  1. 把边们从小到大排个序
  2. 如果没有回路，一条一条往里加
  3. 边数达到（n-1）条，完成

步骤都弄懂啦！但是这个“回路”到底怎么判断呢？

所谓判断回路，就是看看有了这条边之后，有没有连通的部分，从“树”的角度来看，就是两个点的根节点（也就是“祖宗”）是不是一样的

哎？话说说到这里，诸位有没有联想到什么啊？

没错，就是金光闪闪的并！查！集！

并查集是啥就不在我的责任范围之内啦，（其实就是懒癌犯了）这里我就默认泥萌都会并查集了......

所以说我们可以搞个并查集出来，然后每加入条边时，先用并查集的“查询”功能，看看两个节点的祖宗是不是一样的，如果不一样就把他俩“合并”，就可以放心大胆的往里加啦~

明白了最小生成树怎么搞，咱来看看这道题：现在大家都知道这题是典型的最小生成树了，但还要注意两个地方：

首先让我们选k朵云做棉花糖，换句话说就是选k个节点构造最小生成树，那不好办！我们都知道，全部n个点的最小生成树有（n-1）条边，那选k个节点就是（n-k）条边呗！

其次就是这个“No Answer”怎么弄的问题，其实也so easy，你想啊，一共就m条边，如果都选完了还没有选出（n-k）条边来，那就是妥妥的No Answer 了

bb了这么多，是时候放代码了！听我这么一讲解，大家应该都理解最小生成树的Kruskal算法了吧！

#include<iostream>
#include<algorithm>  //sort嘛......当然要开万能的algorithm
using namespace std;
struct woyaohongming{ //不要在意这个结构体的名字......它只是用来存储图的而已
    int s,e,w;    //s-start，e-end，代表边上的两个节点，w就是权值费用了
}a[200005];
int f[200005];  //并查集用的f数组
bool cmp(woyaohongming a,woyaohongming b){   //sort排序规则，按费用从低到高排序
    return a.w<b.w;
}
int find(int a){  //并查集的“找祖宗”函数，注意别忘路径压缩
    if(f[a]==a)
    return a;
    else return f[a]=find(f[a]);
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;   //输入n、m、k，没啥好讲的
    for(int i=1;i<=n;i++)   
    f[i]=i;  //并查集数组初始化，每个节点的祖宗一开始是它自己
    for(int i=1;i<=m;i++)
    cin>>a[i].s>>a[i].e>>a[i].w;  //输入图的信息
    sort(a+1,a+1+m,cmp);   //快活的按权值排个序
   int cnt=0,sum=0;  //cnt是已经选中的边数，sum是最终要输出的最小权值
    for(int i=1;i<=m;i++){   //m条边，循环m次
        if(find(a[i].s)!=find(a[i].e)){ //如果俩节点的祖宗不相等（也就是不是回路），就可以加进去
            f[find(a[i].s)]=find(a[i].e); //把它俩合并成一个祖宗
            sum+=a[i].w;    //更新最小费用
            cnt++; //边数+1
        }
        if(cnt>=n-k)  //边数到达（n-k）条边，任务完成，break
        break;
    }
    if(cnt>=n-k)   //如果选了n-k条边，可以搞最小生成树
    cout<<sum;  //输出最小权值
    else cout<<"No Answer";  //要不然选了m条边还都搞不好，不能构成最小生成树
    return 0;  //终于完事了
}

The End ......

and Happy New Year!