（补+改）~-5 公路村村通

7-5 公路村村通（30 分）
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12

这题我那时来不及做了...以我的水平，只会用邻接矩阵+dfs做

#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

const int mxn = 1105;
int a[mxn][mxn],n, book[mxn],mini = 999999, ext = 0;

void dfs(int c, int cnt, int num){
    if(num >= mini) return;
    if(cnt == n-1){
        ext = 1;
        //printf("%d %d ", mini,num);
        mini = num;
        return;
    }
    //book[c] = 1; //不能在这里标记，应该在函数外标记
    cnt++;
    for(int i = 1; i <=n ; i++){
        if(!book[i] && a[c][i] >= 1){
            //num += a[c][i];  //这里的num不能更新
            book[i] = 1;
            dfs(i, cnt, num + a[c][i]);
            book[i] = 0;
        }
    }
}

int main(){
    int num1,num2,price,road;
    scanf("%d %d", &n,&road);
    memset(a, -1, sizeof(a));
    while(road--){
        scanf("%d %d %d", &num1, &num2, &price);
        a[num1][num2] = price;
        a[num2][num1] = price;
    }
    
    for(int i = 1; i <= n; i++){
        a[i][i] = 0;
    }
    
    for(int i = 1; i <= n; i++){
        memset(book,0,sizeof(book));
        book[i] = 1;
        dfs(i , 0, 0);
    }
    if(ext) printf("%d", mini);
    else    printf("-1");
    return 0;
}

学长代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <stack>

using namespace std;
int n,m;
struct edge
{
    int x,y,cost;
};
typedef struct edge edge;
edge a[3005];
int cmp(edge aa,edge bb)
{
    return aa.cost<bb.cost;
}
int fa[1005];
int Find(int x)
{
    if(fa[x]==x) return x;
    else return fa[x]=Find(fa[x]);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].cost);
    }
    sort(a,a+m,cmp);
    for(int i=0;i<=n;i++)
    {
        fa[i]=i;
    }
    int ans=0;
    int cnt=0;
    for(int i=0;i<m;i++)
    {
        int x=a[i].x;
        int y=a[i].y;
        int cost=a[i].cost;
        int aa=Find(x);
        int bb=Find(y);
        if(aa!=bb)
        {
            fa[aa]=bb;
            ans+=cost;
            cnt++;
            if(cnt==n-1)
            {
                break;
            }
        }
    }
    if(cnt<n-1)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n",ans);
    }


    return 0;
}