7-11 特殊最小成本修路 (10分)（HBU寒假训练营）

200 阅读 0 评论 132 点赞

我是靠谱客的博主潇洒薯片，这篇文章主要介绍7-11 特殊最小成本修路 (10分)（HBU寒假训练营），现在分享给大家，希望可以做个参考。

n个城镇之间目前有一些道路连接，但道路都是年久失修的土道。现在政府准备将其中一些土道改造为标准公路，希望标准公路能够将所有城镇连通且总成本最小，但其中有一个城镇比较特殊，受地形等限制，最多只能有两条标准公路通过该镇。请编写程序，找出一种满足上述条件的、总成本最小的改造方案，若不存在改造方案，则亦能识别。假定道路是双向的。

输入格式:

输入包含多组数据。每组数据第一行是3个整数n、v和e，均不超过50，n为城镇数目，城镇编号0至n-1。v为最能有两条标准公路的城镇编号，e为现有的土路条数，接下来是e行表示每条道路信息，每行为3个非负整数a、b、c，表示城镇a和城镇b间现有一条道路，若将其改造为标准公路，成本为c。

输出格式:

对每组数据输出一行，为一个整数，表示满足要求的最小成本，若不存在改造方案，则输出-1。

输入样例:

复制代码

输出样例:

复制代码

代码：主要采用克鲁斯卡尔算法，寻找最小生成树

复制代码

#include<bits/stdc++.h>
using namespace std;
typedef struct enode
{
    int a;
    int b;
    int cost;
}Enode;
int father[55];
bool cmp(Enode a, Enode b)
{
    if(a.cost<b.cost){
        return true;
    }else{
        return false;
    }
}
int find(int x)
{
    int a = x ;
    while(x!=father[x]){
        x=father[x];
    }
    while(a!=father[a])
    {
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
int main()
{
    int n,v,e;
    while(cin>>n>>v>>e)
    {
        Enode s[e];
        int i;
        for(i=0;i<e;i++){
            cin>>s[i].a>>s[i].b>>s[i].cost;
        }
        sort(s,s+e,cmp);
        for(i=0;i<55;i++){
            father[i]=i;
        }
        int count=0;
        int num=0;
        int sum=0;
        for(i=0;i<e;i++){
            if(s[i].a==v||s[i].b==v){
                int fa=find(s[i].a);
                int fb=find(s[i].b);
                if(count<2 && fa!=fb){
                    count++;
                    num++;
                    sum+=s[i].cost;
                    father[fa]=fb;
                }
            }else if(s[i].a!=v && s[i].b!=v){
                int fa=find(s[i].a);
                int fb=find(s[i].b);
                if(fa!=fb){
                    num++;
                    sum+=s[i].cost;
                    father[fa]=fb;
                }
            }
            if(num == n-1){
                break;
            }  
        }
        if(num==n-1){
            cout<<sum<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
typedef struct enode
{
    int a;
    int b;
    int cost;
}Enode;
int father[55];
bool cmp(Enode a, Enode b)
{
    if(a.cost<b.cost){
        return true;
    }else{
        return false;
    }
}
int find(int x)
{
    int a = x ;
    while(x!=father[x]){
        x=father[x];
    }
    while(a!=father[a])
    {
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
int main()
{
    int n,v,e;
    while(cin>>n>>v>>e)
    {
        Enode s[e];
        int i;
        for(i=0;i<e;i++){
            cin>>s[i].a>>s[i].b>>s[i].cost;
        }
        sort(s,s+e,cmp);
        for(i=0;i<55;i++){
            father[i]=i;
        }
        int count=0;
        int num=0;
        int sum=0;
        for(i=0;i<e;i++){
            if(s[i].a==v||s[i].b==v){
                int fa=find(s[i].a);
                int fb=find(s[i].b);
                if(count<2 && fa!=fb){
                    count++;
                    num++;
                    sum+=s[i].cost;
                    father[fa]=fb;
                }
            }else if(s[i].a!=v && s[i].b!=v){
                int fa=find(s[i].a);
                int fb=find(s[i].b);
                if(fa!=fb){
                    num++;
                    sum+=s[i].cost;
                    father[fa]=fb;
                }
            }
            if(num == n-1){
                break;
            }  
        }
        if(num==n-1){
            cout<<sum<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
    return 0;
}