F. 汤圆防漏理论
2024-09-18 09:50:09
ghc很喜欢吃汤圆,但是汤圆很容易被粘(zhān)漏。
根据多年吃汤圆经验,ghc总结出了一套汤圆防漏理论:
互相接触的汤圆容易粘(zhān)在一起,并且接触面积不同,粘(zhān)在一起的粘(nián)度也不同。
当ghc要夹起一个汤圆时,这个汤圆和现在碗里与这个汤圆接触的所有汤圆之间的粘(nián)度的和,如果大于汤圆的硬度,这个汤圆就会被粘(zhān)漏。
今天ghc又要煮汤圆啦,今天要煮个汤圆,并且摆盘的方法已经设计好:
汤圆按照编号,有对汤圆互相接触,用表示编号为和的两个汤圆互相接触,粘(nián)度为。
汤圆当然是越软越好吃,但是ghc的厨艺只允许把所有汤圆煮成同样的硬度。那么,汤圆的硬度最小可以是多少,可以满足吃的过程中,存在一种夹汤圆的顺序,使得没有汤圆会被粘(zhān)漏呢?
注意:
不考虑汤圆的重力作用;
不能同时夹多个汤圆;
吃完汤圆一定要喝点汤。
Input
第一行是一个正整数,表示测试数据的组数,
对于每组测试数据,
第一行是两个整数,
接下来行,每行包含三个整数,
同一对汤圆不会出现两次。
Output
对于每组测试数据,输出一行,包含一个整数,表示汤圆硬度的最小值。
Sample Input
1
4 6
1 2 2
1 3 2
1 4 2
2 3 3
2 4 3
3 4 5
Sample Output
6
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + ; using LL = long long;
using P = pair<LL, int>; LL cnt[N];
int n, m; set<P> edge[N]; priority_queue<P, vector<P>, greater<P> > Q; void Work(){
LL ans = ;
for(int i = ; i <= n; i++){
Q.push({cnt[i], i});
}
while(!Q.empty()){
auto tmp = Q.top(); Q.pop();
if(tmp.first != cnt[tmp.second]) continue;
int u = tmp.second;
ans = max(ans, tmp.first);
for(auto p : edge[u]){
int v = p.second;
cnt[v] -= p.first;
edge[v].erase({p.first, u});
Q.push({cnt[v], v});
}
}
cout << ans << endl;
} int main(){
int T;
cin >> T;
while(T--){
cin >> n >> m;
for(int i = ; i <= n; i++) {
edge[i].clear();
cnt[i] = ;
} int u, v, w;
for(int i = ; i <= m; i++){
cin >> u >> v >> w;
cnt[u] += w;
cnt[v] += w;
edge[u].insert({w, v});
edge[v].insert({w, u});
}
Work();
} }
最新文章
- 关于so文件cp覆盖导致调用者core的研究
- arcgis api for flex之专题图制作(饼状图,柱状图等)
- JAVA 1.7 流程控制语句 续
- dede日期时间标签调用大全
- Spring学习总结(二)——静态代理、JDK与CGLIB动态代理、AOP+IoC
- 代码片段 - Golang 创建 .tar.gz 压缩包
- iOS开发-网络框架-b
- LeetCode_Next Permutation
- Servlet实现Session
- Chapter 5. Label and Entry Widgets 标签和输入部件
- JSP中的相对路径和绝对路径(转)
- java jquery 函数多參数传递
- 一条命令解决: sql server 2008 安装提示重启计算机
- JDK开发环境搭建及环境变量配置
- libreoffice python 操作word及excel文档
- 编写高质量java代码151个建议
- CentOS下搭建Hive
- wordpress配置通过IP直接访问及apache的配置
- Android-通知栏上的RemoteView
- Java 使用 DBCP mysql 连接池 做数据库操作
热门文章
- 1.RabbitMq - Work 模式
- 【APUE】第3章 文件I/O (3) 文件共享、原子操作、函数dup/dup2、函数sync/fsync/fdatasync、函数fcntl、函数ioct1、目录/dev/fd 使用说明
- 【零基础】彻底搞懂51单片机各种型号(ATMEL系列)
- 提交本地文件至gitlab已有的项目中(更新gitlab)
- 实验吧中围在栅栏中的爱-------writeup
- LC 740. Delete and Earn
- ubuntu更换源的方法
- 10 MySQL之数据备份与恢复
- golang 中国代理
- Spring下使用Redis