[2018.12.27]BZOJ4690 Never Wait for Weights

朱雀 2021-12-23 22:35 89阅读 0赞

首先我们发现UNKNOWN很好判断,写个并查集就好了。

考虑如何算出同一并查集内任意元素的权值差。

设两点\\(a,b\\),另一点\\(c\\)

则答案\\(b-a=(b-c)-(a-c)\\)

发现\\(c\\)可以是同一并查集中任意的点。

考虑使用这个并查集的根。

记\\(f\_x\\)为并查集中\\(x\\)的父亲,\\(d\_x\\)为第\\(x\\)个样品比它的父亲这个样品轻多少。

则我们在将\\(x\\)的父亲更新到\\(f\_\{f\_x\}\\)时,要将\\(d\_x\\)设为\\(d\_x+d\_\{f\_x\}\\)。

合并类似,但是我太懒难以表述,所以可以自己看代码(应该很清楚吧?)。

code:

#include<bits/stdc++.h> using namespace std; int n,m,a,b,w,f[100010],d[100010]; char op; void getc(char &c){ c=getchar(); while(c!='!'&&c!='?')c=getchar(); } int getf(int x){ if(f[x]==x)return x; int t=getf(f[x]); d[x]+=d[f[x]]; return f[x]=f[f[x]]; } void merge(int x,int y,int v){ if(getf(x)==getf(y))return; d[f[x]]=v-d[x]+d[y]; f[f[x]]=f[y]; } int main(){ while(scanf("%d%d",&n,&m)){ if(!n)return 0; for(int i=1;i<=n;i++)f[i]=i,d[i]=0; while(m--){ getc(op); if(op=='!')scanf("%d%d%d",&a,&b,&w),merge(a,b,w); else{ scanf("%d%d",&a,&b); if(getf(a)!=getf(b))puts("UNKNOWN"); else printf("%d\n",d[a]-d[b]); } } } return 0; }

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ4690.html

发表评论取消回复

表情：

评论列表（有 0 条评论，89人围观）

还没有评论，来说两句吧...

相关阅读

相关异常篇 - Waiting for Debugger 解决

解决办法: 方式一: Run —> Attach debugger to Android process 方式二: 打开开发者选项，选择调试应用，这个功能，点击添加进

桃扇骨/ 2023年10月08日 10:06/ 0 赞/ 49 阅读

相关 Waiting for table metadata lock

mysql查询卡死，从navicat客户端查看“服务器监控”看到state有很多“Waiting for table metadata lock”。我的解决方式就是kill

今天药忘吃喽~/ 2022年12月24日 02:58/ 0 赞/ 106 阅读

相关 docker-compose使用wait-for-it

nacos地址 [http://192.168.32.136:8848/nacos/][http_192.168.32.136_8848_nacos] 账号:nacos

我不是女神ヾ/ 2022年11月09日 11:23/ 0 赞/ 160 阅读

相关 waiting for changelog lock.

> 一般情况下是数据库liquibase被锁， > > ![20210719170026287.png][] > > 可以按照以下方式解决 > > 数据库执行： >

╰半夏微凉°/ 2022年08月30日 06:22/ 0 赞/ 223 阅读

相关 Android fastboot waiting for devices

The short version of the page linked by D Shu (and without the horrible popover ads) is

素颜马尾好姑娘i/ 2022年08月06日 09:20/ 0 赞/ 98 阅读

相关 mysql Waiting for table metadata lock

当我们在进行表的更新操作或者是想要drop table的操作的时候,有时候,会卡死,这样的原因在于事务还未提交或者未回滚。但是此时有其他的用户在执行表的ddl语句。 (更新表

朱雀/ 2022年06月10日 12:23/ 0 赞/ 198 阅读

相关 androidstudio "waiting for debugger" 卡住

androidstudio 设断点调试卡在 "waiting for debugger" 试过好多方法无效 adb kill server 什

浅浅的花香味﹌/ 2022年06月07日 00:35/ 0 赞/ 294 阅读

相关 HYSBZ 4690 Never Wait for Weights（变种并查集）

在实验室中，Nathan Wada作为助手的职责是测定两个样品的重量差异。当样品的差异很小时，使用天平能比使用弹簧秤得到更精确的结果，所以他只使用天平来测得一些样品的重量差

ゝ一纸荒年。/ 2022年06月04日 03:57/ 0 赞/ 86 阅读

相关 MySQL5.7 Waiting FOR TABLE FLUSH

系统不能使用，数据库上99%的会话等待是Waiting FOR TABLE FLUSH，找到等待时间最长的会话kill，系统恢复正常。是什么原因造成的呢？日志分析： T

Bertha 。/ 2022年04月03日 09:41/ 0 赞/ 362 阅读

相关 [2018.12.27]BZOJ4690 Never Wait for Weights

首先我们发现UNKNOWN很好判断,写个并查集就好了。考虑如何算出同一并查集内任意元素的权值差。设两点\\(a,b\\),另一点\\(c\\) 则答案\\(b-a=(

朱雀/ 2021年12月23日 22:35/ 0 赞/ 90 阅读