题目在这

Sample Input

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1 

Sample Output

1 4 1 2 1 3 2 3 3 4

题目意思:4个点,6个边,每个边有对应的权值。最后输出一行为路径中最大的边的值,第二行为路径上边的总数,

第三行为每条边的始末编号。题目需要求出最小生成树的最大边的最小值。

POJ1861(Network)-Kruskal 算法 第1张
 1 /*
 2 Problem: 1861        User: 
 3 Memory: 416K        Time: 500MS
 4 Language: C++        Result: Accepted
 5 */
 6 #include <iostream>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 #define MAX 15010
11 int p[1010];//存放父亲结点
12 
13 struct Edge
14 {
15     int u;
16     int v;
17     int w;
18 }map[MAX],ans[MAX];
19 
20 bool cmp(Edge a,Edge b)
21 {
22     return a.w<b.w;
23 }
24 
25 int Find(int a)
26 {
27     return a==p[a]?a:a=Find(p[a]);
28 }
29 
30 int main()
31 {
32     int N,M,i;
33     int a,b,c;
34     cin>>N>>M;
35     for(i=0;i<=N;i++)
36     {
37         p[i] = i;
38     }
39     for(i=0;i<M;i++)
40     {
41         cin>>a>>b>>c;
42         map[i].u = a;
43         map[i].v = b;
44         map[i].w = c;
45     }
46     sort(map,map+M,cmp);
47     int count = 0;
48     int maxEdge = 0;
49     for(i=0;i<M;i++){
50         int x = Find(map[i].u);
51         int y = Find(map[i].v);
52         if(x != y)
53         {
54             p[x] = y;//不在一个集合,合并
55             ans[count].u = map[i].u;
56             ans[count].v = map[i].v;
57             count ++;
58             if(map[i].w>maxEdge)
59                 maxEdge = map[i].w;
60         }
61     }
62     cout<<maxEdge<<endl;//路径中最长的边
63     cout<<count<<endl;//边的总数
64     for(i=0;i<count;i++)
65         cout<<ans[i].u<<" "<<ans[i].v<<endl;/输出每条路径
66     return 0;
67 }
View Code

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄