汤圆防漏理论-白红宇

汤圆防漏理论

阅读量：4646 次

发布时间：2019-06-09

本文共 1857 字，大约阅读时间需要 6 分钟。

链接：

来源：牛客网

ghc很喜欢吃汤圆，但是汤圆很容易被粘(zhān)漏。

根据多年吃汤圆经验，ghc总结出了一套汤圆防漏理论：

互相接触的汤圆容易粘(zhān)在一起，并且接触面积不同，粘(zhān)在一起的粘(nián)度也不同。

当ghc要夹起一个汤圆时，这个汤圆和现在碗里与这个汤圆接触的所有汤圆之间的粘(nián)度的和，如果大于汤圆的硬度，这个汤圆就会被粘(zhān)漏。

今天ghc又要煮汤圆啦，今天要煮n个汤圆，并且摆盘的方法已经设计好：

汤圆按照 $1, 2, \dots , n$ 编号，有m对汤圆互相接触，用x_i, y_i, z_i表示编号为x_i和y_i的两个汤圆互相接触，粘(nián)度为z_i。

汤圆当然是越软越好吃，但是ghc的厨艺只允许把所有汤圆煮成同样的硬度。那么，汤圆的硬度最小可以是多少，可以满足吃的过程中，存在一种夹汤圆的顺序，使得没有汤圆会被粘(zhān)漏呢？

注意：

不考虑汤圆的重力作用；

不能同时夹多个汤圆；

吃完汤圆一定要喝点汤。

输入描述:

第一行是一个正整数T(≤ 5)，表示测试数据的组数，

对于每组测试数据，

第一行是两个整数n,m(1≤ n,m≤ 100000)，

接下来m行，每行包含三个整数x_i, y_i, z_i(1≤ x_i, y_i ≤ n, x_i ≠ y_i, 1 ≤ z_i ≤ 1000000)，

同一对汤圆不会出现两次。

输出描述:

对于每组测试数据，输出一行，包含一个整数，表示汤圆硬度的最小值。

示例1

输入

14 61 2 21 3 21 4 22 3 32 4 33 4 5

输出

6 二分硬度

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     #include 
                      
                       using namespace std;#pragma comment(linker, "/stck:1024000000,1024000000")#define lowbit(x) (x&(-x))#define max(x,y) (x>=y?x:y)#define min(x,y) (x<=y?x:y)#define MAX 100000000000000000#define MOD 1000000007#define pi acos(-1.0)#define ei exp(1)#define PI 3.1415926535897932384626433832#define ios() ios::sync_with_stdio(true)#define INF 0x3f3f3f3f#define mem(a) ((a,0,sizeof(a)))typedef long long ll;ll n,m,t,x,y,z;ll a[100006];vector
                       
                        
                          >v[100006];int solve(ll value){ int vis[100006],rvis[100006]; ll mid[100006]; queue
                         
                          q; memset(vis,0,sizeof(vis)); memset(rvis,0,sizeof(rvis)); for(int i=1;i<=n;i++) { mid[i]=a[i]; if(a[i]<=value) { q.push(i); rvis[i]=1; } } while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=1; for(int i=0;i
                          
                           >1; if(!solve(ans)) r=ans-1; else l=ans+1; } printf("%lld\n",l); } return 0;}

转载于:https://www.cnblogs.com/shinianhuanniyijuhaojiubujian/p/8973809.html

你可能感兴趣的文章