最大生成树Bad Cowtractors

题目链接：http://poj.org/problem?id=2377；

 仔细阅读题目，你会发现一个词-" as large as possible"，这个词的意思是尽可能最大； 

来，我们翻译一下题目：

题目大意是

现在有一个人给人修建一些线路，（当然，我们想要少花钱消费，人家就想多多赚你的钱了，现在就给出这么一个问题）。让你求修得所有电路能赚取的最大利润，若电路不能被全部修完，输出“-1”.

那这个题考的是最小生成树的题，但是按照题目要求，我们要改成所谓的最大生成树问题，

即求得生成树的权值是最大的而不是最小的，那该怎么办呢？

其实也很好处理，最小生成树的核心无非是按照边的权值最小逐一将图的权值一一加进生成树里，

那对于这个题来说，就将边的权值最大一一加进树里即可，

所以说，和最小生成树相比，核心就在这:

bool cmp(edge a,edge b)
{
    return a.w>b.w;
}

将原来的按小排序改成按大排序即可。

还有几个点需要注意的是，这个题的依旧是要判断图的联通性，如果联通则输出生成树的权值，如果不连通这次输出-1；

然后根据最小生成树进行改动即可；

Talk is cheap. Show me the code.

 1 #include//poj头文件很烦银
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include
 8 #include
 9 using namespace std;
10 const int num=1e5+10;
11 struct edge
12 {
13     int u;
14     int v;
15     int w;
16 }e[num];//存图
17 int s[num];//集合
18 int n,m;
19 int ans;//生成树权值
20 int cnt;//统计边数
21 bool cmp(edge a,edge b)//降序排列
22 {
23     return a.w>b.w;
24 }
25 int find_set(int x)//集合查找+路径压缩
26 {
27     if(x!=s[x])
28     s[x]=find_set(s[x]);
29     return s[x];
30 }
31 void kruskal()
32 {
33     for(int i=1;i<=n;i++)//集合初始化
34     s[i]=i;
35     sort(e+1,e+1+m,cmp);
36     for(int i=1;i<=m;i++)
37     {
38         int b=find_set(e[i].u);
39         int c=find_set(e[i].v);
40         if(b==c)//如果重边则跳过
41         continue;
42         s[c]=b;//合并集合
43         ans+=e[i].w;//累计权值
44         cnt++;//边+1
45         if(cnt==n-1)//联通至此结束
46         break;
47     }
48 }
49 int main()
50 {
51     cin>>n>>m;
52     for(int i=1;i<=m;i++)
53     {
54         scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
55     }
56     kruskal();
57     if(cnt==n-1)
58     printf("%d\n",ans);
59     else//不连通输出-1
60     printf("%d\n",-1);
61     return 0;
62 }
图论

相关

图论---网络流

数的重心(图论深搜)

电子科技大学《图论及其应用》复习总结--第七章 图的着色

电子科技大学2017年《图论及其应用》试卷及答案

图论算法遍历基础

图论算法与模型（训练指南题库）

图论中的初始值

图论算法-最小生成树

LeetCode题解-07（简单图论）

图论学习笔记（二）

关于树（图论初步）

专题训练3-图论 - B - Learning Languages（并查集）

标签