关键词：
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1640
收藏
关注这样阴沉的天气持续下去，我们不免担心起他的健康。
两个正整数N，M。(1 <= N <= 10^5, N <= M <= 2 * 10^5) 接下来M行，每一行有三个整数A, B, V。(1 <= A, B <= N, INT_MIN <= V <= INT_MAX) 保证输入数据合法。
输出一个正整数R，表示符合条件的魔法阵的魔力值之和。
4 6 1 2 3 1 3 1 1 4 7 2 3 4 2 4 5 3 4 6
12
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 struct Edge 5 { 6 int u,v,w; 7 bool operator<(const Edge &t)const{ 8 return w<t.w; 9 } 10 }e[200005]; 11 int f[100005]; 12 int getf(int v){return f[v]==v?f[v]:f[v]=getf(f[v]);} 13 bool ok(int k,int N,int M) 14 { 15 for(int i=1;i<=N;++i) f[i]=i; 16 for(int i=0;i<M&&e[i].w<=k;i++){ 17 int fu=getf(e[i].u),fv=getf(e[i].v); 18 if(fv!=fu){ 19 N--; 20 f[fv]=fu; 21 } 22 if(N==1) return 1; 23 } 24 return 0; 25 } 26 int main() 27 { 28 int N,M,i,j,l=2147483647,r=0; 29 cin>>N>>M; 30 for(i=0;i<M;++i){ 31 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); 32 l=min(l,e[i].w); 33 r=max(r,e[i].w); 34 } 35 sort(e,e+M); 36 LL ans=0; 37 while(l<r){ 38 int mid=l+((r-l)>>1); 39 if(ok(mid,N,M)){ 40 r=mid; 41 } 42 else{ 43 l=mid+1; 44 } 45 } 46 for(int i=1;i<=N;++i) f[i]=i; 47 Edge e1{-1,-1,l}; 48 int ed=upper_bound(e,e+M+1,e1)-e; 49 for(int i=ed;i>=0;--i){ 50 if(e[i].w>l) continue; 51 int fu=getf(e[i].u),fv=getf(e[i].v); 52 if(fv!=fu){ 53 ans+=e[i].w; 54 N--; 55 f[fv]=fu; 56 } 57 if(N==1) break; 58 } 59 printf("%lld ",ans); 60 return 0; 61 }
51nod1640天气晴朗的魔法(最小生成树)(代码片段)
题目链接解题思路??看这题第一眼就想到了二分，虽然也过了不过还有一个更好的解法。本题的核心就是如何找到那条可以最小的最大的边(S)，二分确实是一个办法，但是还有一种办法是求最小生成树，其最大边就是(S)。??因为... 查看详情
51nod1640(kruscal)
...目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1640 题意：中文题诶～ 思路：kruscal题目要求是在边权最大值最小的情况下总权值尽量大，注意其中的优先级；可以先从小到大加边kruscal一遍得到最小的最大边权，... 查看详情
51nod1640天气晴朗的魔法
题目来源： 原创基准时间限制：1 秒空间限制：131072 KB分值: 20 难度：3级算法题这样阴沉的天气持续下去，我们不免担心起他的健康。 51nod魔法学校近日开展了主题为“天气晴朗”的魔法交流活动。&... 查看详情
51nod1640天气晴朗的魔法（最小生成树）
1640天气晴朗的魔法题目来源：原创基准时间限制：1秒空间限制：131072KB分值:20难度：3级算法题收藏关注取消关注这样阴沉的天气持续下去，我们不免担心起他的健康。 51nod魔法学校近日开展了主题为“天气晴朗”... 查看详情
51nod1601完全图mst计数
我们可以根据二进位划分集合，从高到底，越来越首先，最高位不同的点集合中，必须存在一条边，所以，可以用trie树来处理该操作并统计该边的数目。然后对于两个不同的集合，递归重复这样的操作，就会得到两个集合的MST... 查看详情
51nod1105(二分)
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1105 题意：中文题诶～ 思路：直接二分答案，再通过二分找有多少组合大于等于当前值，确定答案； 代码：1#include<iostream>2#include<stdio.h>3#include<algo 查看详情
51nod1267二分
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=126712674个数和为0基准时间限制：1秒空间限制：131072KB分值:20难度：3级算法题收藏关注给出N个整数，你来判断一下是否能够选出4个数，他们的和为0，可以则输出"Yes"，否则输出"No"... 查看详情
51nod1128二分
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=11281128正整数分组 V2基准时间限制：1秒空间限制：131072KB分值:80难度：5级算法题收藏关注给出一个长度为N的正整数数组，不改变数组元素的顺序，将这N个数分为K组。各组中元... 查看详情
51nod1279(二分)
题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1279 题意：中文题诶～ 思路：就想短板效应一样，很显然决定当前盘子能否到达高度x位置的是井口到x位置的最窄地方能否放下盘子，那么我们可以用vis[i]存储井... 查看详情
51nod1243排船的问题（二分）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1243题意： 思路：二分来做，每次贪心的把船安排到能安排的最左边即可。1#include<iostream>2#include<algorithm>3#include<cstring>4#include<cstdio> 查看详情
51nod1287(二分线段树)
...ttps://www.51nod.com/onlineJudge/questionCode.html#!problemId=1287思路：二分查找大于等于b[i]的最前面的位置（想起一次错漏百出的网赛中一道没在比赛A掉的题），并更新线段树，总复杂度nlogn。我并不是停留在舒适区，而是找回当年因为死... 查看详情
51nod1243二分+贪心
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=12431243排船的问题题目来源：Codility基准时间限制：1秒空间限制：131072KB分值:40难度：4级算法题收藏关注一个码头中有N艘船和N个木桩，船的长度为2*X，码头的宽度为M，N个木桩的位... 查看详情
51nod1010(枚举+二分)
题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1010 题意：中文题诶～ 思路：求第一个比x(1<=x<=1e18)大或者等于的数y,且y的因子只有2,3,5，即y=pow(2,i)*pow(3,j)*pow(5,k);那么显然我们可以通过枚举i,j,k求出所有由2... 查看详情
51nod125701分数规划/二分
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=12571257背包问题 V3基准时间限制：3秒空间限制：131072KB分值:80难度：5级算法题收藏关注N个物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数），... 查看详情
51nod1105二分好题
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=11051105第K大的数基准时间限制：1秒空间限制：131072KB分值:40难度：4级算法题收藏关注数组A和数组B，里面都有n个整数。数组C共有n^2个整数，分别是A[0]*B[0],A[0]*B[1]......A[1]*B[0],A[1]*B[1]... 查看详情
51nod10903个数和为0(排序+二分）
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1090 首先将序列进行排序，然后根据a+b+c=0,c=-a-b,二分查找c，注意判重，即c>b。时间复杂度O(n*n*logn)。#include<bits/stdc++.h>usingnamespacestd;intn,a[1005];in 查看详情
51nod2006飞行员配对（二分图最大匹配）
链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=2006思路：二分匹配注意nm的关系代码：1#include<iostream>2#include<string.h>3usingnamespacestd;4intg[105][105],vis[105],who[105];5intn,m;6bo 查看详情
51nod1010stl/数论/二分
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=10101010只包含因子235基准时间限制：1秒空间限制：131072KB分值:10难度：2级算法题收藏关注K的因子中只包含235。满足条件的前10个数是：2,3,4,5,6,8,9,10,12,15。所有这样的K组成了一个序... 查看详情