战争通讯题解，核心代码量较低(不到30行)

解题思路:

本题基于克鲁斯卡尔算法，执行流程也与克鲁斯卡尔算法基本一致。

不同的地方在于，克鲁斯卡尔算法最终会形成一颗最小生成树，而本题最终结果可能会是多个小生成树，和多个单独的结点，也可以把这些单独的点看作小生成树。

注意事项:

选择边的时候，也要和克鲁斯卡尔算法一样，从小到大选，并且不能构成回路。

同时还需要判断，选择这条边以后，对于这条边两侧的小生成树来说，总的值会不会比不加这条边更小，如果是更小则选择这条边，否则不选择。

选择边了以后，合并两侧的小生成树，根结点使用权值更小的。

最后没有选上边的结点，它们就是单独的结点作为小生成树，自己就作为电台，而其他选上边的小生成树来说，使用根结点作为电台，在上面的执行过程中，每次合并都使用权值最小的结点作为根结点。

最终的值就是选中的边的值，加上所有小生成树的根结点的值，end。

参考代码:

#include<stdio.h>
#include<algorithm> 
namespace std;
int node_nums;
int node_value[50];
int m[50][50];
int side_nums;
struct side
{
    int a;
    int b;
    int value;
};
struct side side_arr[2500];
class Comp
{
public:
    bool operator()(const struct side &side1,const struct side &side2)
    {
        return side1.value < side2.value;
    }
};
int node_set[50];
void init()
{
    for(int i = 0;i < node_nums;i++){
        node_set[i] = i;
    }
}
int get_root(int index)
{
    while(index != node_set[index]){
        index = node_set[index];
    }
    return index;
}
int mv;
void krus()
{
    int root1,root2,root_value1,root_value2;
    for(int i = 0;i < side_nums;i++){
        root1 = get_root(side_arr[i].a);
        root2 = get_root(side_arr[i].b);
        if(root1 == root2){
            continue;
        }
        root_value1 = node_value[root1];
        root_value2 = node_value[root2];
        if(root_value1 > root_value2){
            if(side_arr[i].value <= root_value1){
                mv += side_arr[i].value;
                node_set[root1] = root2;
            }
        }else{
            if(side_arr[i].value <= root_value2){
                mv += side_arr[i].value;
                node_set[root2] = root1;
            }
        }
    }
}
int main()
{
    scanf("%d",&node_nums);
    for(int i = 0;i < node_nums;i++){
        scanf("%d",&node_value[i]);
    }
    int temp_v;
    for(int i = 0;i < node_nums;i++){
        for(int j = 0;j < node_nums;j++){
            scanf("%d",&temp_v);
            if(i < j){
        side_arr[side_nums].value = temp_v;
        side_arr[side_nums].a = i;
        side_arr[side_nums].b = j;
        side_nums++;
        }
    }
    }
    sort(side_arr,side_arr+side_nums,Comp());
    init();
    krus();
    for(int i = 0;i < node_nums;i++){
    if(i == get_root(i)){
        mv += node_value[i];
    }
    }
    printf("%d\n",mv);
    return 0;
}
//最近离职在家，没事刷刷题，这题搞了一天才搞出来