网站空间多少钱一年,网络宣传的方法有哪些,安卓手机做服务器网站,wordpress 网站播放器插件下载坏的牛圈建筑 题目大意#xff1a;就是现在农夫又要牛修建牛栏了#xff0c;但是农夫想不给钱#xff0c;于是牛就想设计一个最大的花费的牛圈给他#xff0c;牛圈的修理费用主要是用在连接牛圈上 这一题很简单了#xff0c;就是找最大生成树#xff0c;把Kruskal算法改一… 坏的牛圈建筑 题目大意就是现在农夫又要牛修建牛栏了但是农夫想不给钱于是牛就想设计一个最大的花费的牛圈给他牛圈的修理费用主要是用在连接牛圈上 这一题很简单了就是找最大生成树把Kruskal算法改一下符号就好了把边从大到小排列然后最后再判断是否联通只要找到他们的根节点是否相同就可以了 1 #include iostream2 #include algorithm3 #include functional4 #define MAX_N 10055 #define MAX 200056 7 using namespace std;8 9 typedef int Position;10 typedef struct _edge11 {12 Position from;13 Position to;14 int cost;15 }Edge_Set;16 int fcomp(const void *a, const void *b)17 {18 return (*(Edge_Set *)b).cost - (*(Edge_Set *)a).cost;19 }20 21 static Edge_Set edge[MAX];22 static Position Set[MAX_N];23 24 Position Find(Position);25 void Union(Position, Position);26 void Kruskal(const int, const int);27 bool Is_Connected(const int);28 29 int main(void)30 {31 int Node_Sum, Path_Sum, cost;32 Position tmp_from, tmp_to;33 34 while (~scanf(%d%d, Node_Sum, Path_Sum))35 {36 for (int i 0; i Path_Sum; i)//读入边37 {38 scanf(%d%d%d, tmp_from, tmp_to, cost);39 edge[i].from tmp_from; edge[i].to tmp_to; edge[i].cost cost;40 }41 qsort(edge, Path_Sum, sizeof(Edge_Set), fcomp);42 Kruskal(Node_Sum, Path_Sum);43 }44 return 0;45 }46 47 Position Find(Position x)48 {49 if (Set[x] 0)50 return x;51 else return Set[x] Find(Set[x]);52 }53 54 void Union(Position px, Position py)55 {56 if (Set[px] Set[py])57 {58 Set[px] Set[py];59 Set[py] px;60 }61 else62 {63 Set[py] Set[px];64 Set[px] py;65 }66 }67 68 bool Is_Connected(const int Node_Sum)69 {70 Position p_u, p_tmp;71 p_u Find(1);72 for (int i 2; i Node_Sum; i)73 {74 p_tmp Find(i);75 if (p_u ! p_tmp)76 return false;77 }78 return true;79 }80 81 void Kruskal(const int Node_Sum, const int Path_Sum)82 {83 Position px, py, from, to;84 long long ans 0;85 86 fill(Set, Set Node_Sum 1, -1);87 for (int i 0; i Path_Sum; i)88 {89 from edge[i].from; to edge[i].to;90 px Find(from); py Find(to);91 92 if (px ! py)93 {94 ans edge[i].cost;95 Union(px, py);96 }97 }98 if (Is_Connected(Node_Sum))99 printf(%lld\n, ans);
100 else
101 printf(-1\n);
102 } 转载于:https://www.cnblogs.com/Philip-Tell-Truth/p/4955944.html
