【数据结构】最⼩⽣成树（四）——利⽤kruskal算法搞定例题×3+变形+⼀道⼤⽔题
  在这⼀专辑（最⼩⽣成树）中的上⼀期讲到了prim算法，但是prim算法⽐较难懂，为了避免看不懂，就先⽤kruskal算法写题吧，下⾯将会将三道例题，加⼀道变形，以及⼀道⼤⽔题，⽔到不⽤⾼级数据结构，建树，画图，最短路径什么的，统统不需要。废话不多说，直接看题：
1.例题精讲
T1：
1348：【例4-9】城市公交⽹建设问题
时间限制: 1000 ms        内存限制: 65536 KB
提交数: 2094    通过数: 650
【题⽬描述】
有⼀张城市地图，图中的顶点为城市，⽆向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建⾼速公路的造价，研究后发现，这个地图有⼀个特点，即任⼀对城市都是连通的。现在的问题是，要修建若⼲⾼速公路把所有城市联系起来，问如何设计可使得⼯程的总造价最少？
【输⼊】
n（城市数，1<≤n≤100）
e（边数）
以下e⾏，每⾏3个数i,j,wiji,j,wij，表⽰在城市i,j之间修建⾼速公路的造价。
【输出】
n-1⾏，每⾏为两个城市的序号，表明这两个城市间建⼀条⾼速公路。
【输⼊样例】
5 8
1 2 2
2 5 9
5 4 7
4 1 10
1 3 12
4 3 6
5 3 3
2 3 8
【输出样例】
1  2
2  3
3  4
3  5
  看完之后有思路吗？这题肯定简单，这是⼀道纯模板题，只不过输出有点⿇烦。总之，先来回忆⼀下kr
uskal算法原理：⾸先需要到图中的⼀条最短的边，如果它不与最⼩⽣成树集合中的其他边产⽣回路，那么就加⼊这条边⾄集合中，上次⼩编写的很草率，只是⼀个伪代码（伪代码如下），这次的题⽬⼩编会写成正式代码；接着，输出⼜是⼀个⿇烦事，这就需要分析样例了，先好好看⼀看样例，你发现了吗？左边的数总⼩于右边的数，下⾯的第⼀个数总⽐上⾯的第⼀个数⼤，当然，如果第⼀个数⼀样⼤，那么就按第⼆个数从⼩到⼤排序。依据这个规律，接着，就来看⼀看AC代码吧。
1//假设MST[]是最⼩⽣成树的集合，cnt表⽰是存⼊集合的边数
2while(cnt<n-1)//共有n-1条边
3 {
4在图中出最短的⼀条边;
5if(添加这条边不产⽣回路)
6    {
7加⼊MST集合;
8        cnt++;
9    }
10 }
//伪代码
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<cmath>
5 #include<algorithm>
6using namespace std;
7int n,e,a[1000],k,p,q;
8struct tree{
9int start;
10int end;
11int cost;
12 };
13 tree T[1000];
14bool operator < (const tree& a,const tree& b)//按cost的值从⼩到⼤排序
15 {
st&st;
17 }
18bool cmp(tree a,tree b)//这个排序⽅式就是上⾯所说的关系
19 {
20if(a.start==b.start)
d&d;
22return a.start<b.start;
23 }
24 priority_queue<tree>t;
25 inline int find(int x)//26 {
27if(x==a[x]) return x;
28else return a[x]=find(a[x]);
29 }
30void kruskal()
31 {
32for(int i=1;i<=n;i++)//并查集初始化
33    a[i]=i;
34    tree large;
35for(int i=1;i<=e;i++)
36    {
37        p();//获取最⼩边
38        t.pop();
39if(find(large.start)!=d))//如果不产⽣回路
40        {
41            p=find(large.start);q=d);
42            a[q]=p;
43            T[++k]=large;//加⼊到集合中
44        }
45    }
46    sort(T+1,T+k+1,cmp);//按规律排序，否则顺序不对
47for(int i=1;i<=k;i++)
48    printf("%d %d \n",T[i].start,T[i].end);
49 }
50int main()
51 {
52    tree s;
53    scanf("%d%d",&n,&e);
54for(int i=1;i<=e;i++)
55    {
56        scanf("%d%d%d",&s.start,&d,&st);
57if(s.start&d) swap(s.d);
58        t.push(s);
59    }
60    kruskal();
61return0;
62 }
//AC代码
  这个代码虽然看起来很长，但是效率很⾼，如果⽤数组来存储，代码确实精简了，看起来确实易懂了，
但是很浪费时间，每⼀次的最⼩边都要花O（n）的时间去寻，如果⽤堆（优先队列），直接询问队顶元素就可以了。如果你并不清楚⽤着结构体的优先队列，就⼀定不会理解以下这段代码的意思，这段代码表⽰按cost的值进⾏排序，因为结构体中有三个元素，不这么写就⽆法按你的⼼意排序。
14 bool operator < (const tree& a,const tree& b)
15 {
16    st&st;
17 }
T2:
1349：【例4-10】最优布线问题
时间限制: 1000 ms        内存限制: 65536 KB
提交数: 1228    通过数: 733
【题⽬描述】
学校有n台计算机，为了⽅便数据传输，现要将它们⽤数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费⽤往往是不同的。
当然，如果将任意两台计算机都⽤数据线连接，费⽤将是相当庞⼤的。为了节省费⽤，我们采⽤数据的间接传输⼿段，即⼀台计算机可以间接的通过若⼲台计算机（作为中转）来实现与另⼀台计算机的连接。
现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。
【输⼊】
第⼀⾏为整数n（2≤n≤100），表⽰计算机的数⽬。此后的n⾏，每⾏n个整数。第x+1⾏y列的整数表⽰直接连接第x台计算机和第y台计算机的费⽤。
【输出】
⼀个整数，表⽰最⼩的连接费⽤。
【输⼊样例】
3
0 1 2
1 0 1
2 1 0
【输出样例】
2
  这道题和刚才的题出⾃同⼀个⽅法，似乎⽤prim算法更好，不知道你刚才的代码还留着吗？其实刚才的代码稍加改动，这道题就能过了，下⾯来分析⼀下这道题与刚才的题的异同点，⾸先输⼊⼀定是不同的，要输⼊⼀个矩阵，所以这⾥要改⼀下；还有这道题只求和，不求每⼀条边，这可是⼀个福利，不⽤像刚才⼀样⿇烦了，总之，废话不多说，AC代码呈上：
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<cmath>
5 #include<algorithm>
6using namespace std;
7int n,e,a[1000],k,p,q,ans,map[1000][1000];
8struct tree{
9int start;
10int end;
11int cost;
12 };
13//tree T[1000];
14bool operator < (const tree& a,const tree& b)
15 {
st&st;
17 }
18bool cmp(tree a,tree b)
19 {
20if(a.start==b.start)
d&d;
22return a.start<b.start;
23 }
24 priority_queue<tree>t;
25 inline int find(int x)
26 {
27if(x==a[x]) return x;
28else return a[x]=find(a[x]);
29 }
30void kruskal()
31 {
32for(int i=1;i<=n;i++)
33    a[i]=i;
34    tree large;
35for(int i=1;i<=e;i++)
36    {
37        p();
38        t.pop();
39if(find(large.start)!=d))
40        {
41            p=find(large.start);q=d);
42            a[q]=p;
43            ans+=st;
44        }
45    }
46 }
47int main()
48 {
49    tree s;
50    scanf("%d",&n);
51for(int i=1;i<=n;i++)
52for(int j=1;j<=n;j++)
53    {
54        scanf("%d",&map[i][j]);
55        s.start=i;
56        s.end=j;
57        s.cost=map[i][j];
58        t.push(s);
59if(i!=j)
60        e++;
61    }
62    kruskal();
63    printf("%d",ans);
64return0;
65 }
  具体就不怎么介绍了，这也是⼀道纯模板题，如果你想练⼿，可以先写⼀写下⾯这道题。
T3：
1350：【例4-11】最短⽹络(agrinet)
时间限制: 1000 ms        内存限制: 65536 KB
提交数: 1054    通过数: 711
【题⽬描述】
农民约翰被选为他们镇的镇长！他其中⼀个竞选承诺就是在镇上建⽴起互联⽹，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了⼀条⾼速的⽹络线路，他想把这条线路共享给其他农场。为了⽤最⼩的消费，他想铺设最短的光纤去连接所有的农场。你将得到⼀份各农场之间连接费⽤的列表，你必须出能连接所有农场并所⽤光纤最短的⽅案。每两个农场间的距离不会超过100000。
【输⼊】
第⼀⾏：农场的个数，N（3≤N≤100）。
第⼆⾏..结尾：后来的⾏包含了⼀个N*N的矩阵，表⽰每个农场之间的距离。理论上，他们是N⾏，每⾏由N个⽤空格分隔的数组成，实际上，他们限制在80个字符，因此，某些⾏会紧接着另⼀些⾏。当然，对⾓线将会是0，因为不会有线路从第i个农场到它本⾝。
【输出】
只有⼀个输出，其中包含连接到每个农场的光纤的最⼩长度。
【输⼊样例】
4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0
【输出样例】
28
  怎么样，你写出来了吗？下⾯是AC代码：
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<cmath>
5 #include<algorithm>
6using namespace std;
7int n,e,a[1000],k,p,q,ans,map[1000][1000];
8struct tree{
9int start;
10int end;
11int cost;
12 };
13//tree T[1000];
14bool operator < (const tree& a,const tree& b)
15 {
31省新增24例输入st&st;
17 }
18bool cmp(tree a,tree b)
19 {
20if(a.start==b.start)
d&d;
22return a.start<b.start;
23 }
24 priority_queue<tree>t;
25 inline int find(int x)
26 {
27if(x==a[x]) return x;
28else return a[x]=find(a[x]);
29 }
30void kruskal()
31 {
32for(int i=1;i<=n;i++)
33    a[i]=i;
34    tree large;
35for(int i=1;i<=e;i++)
36    {
37        p();
38        t.pop();
39if(find(large.start)!=d))
40        {
41            p=find(large.start);q=d);
42            a[q]=p;
43            ans+=st;
44        }
45    }
46 }
47int main()
48 {
49    tree s;
50    scanf("%d",&n);
51for(int i=1;i<=n;i++)
52for(int j=1;j<=n;j++)
53    {
54        scanf("%d",&map[i][j]);
55        s.start=i;
56        s.end=j;
57        s.cost=map[i][j];
58        t.push(s);
59if(i!=j)
60        e++;
61    }
62    kruskal();
63    printf("%d",ans);
64return0;
65 }
  有没有发现什么？和T2⼀模⼀样的代码竟然在T3就过了，我猜出这道题的是为了让我们再⼿敲⼀遍代码加深理解，既然这道题是披着T3⽪的T2，那就不解释了，直接看⼀道变形。
2.⽜⼑⼩试
T4：
1391：局域⽹(net)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。