Never Wait for Weights(带权并查集+路径压缩)
2024-10-14 02:53:28
题目链接:http://acm.sdibt.edu.cn/vjudge/contest/view.action?cid=2209#problem/F
!a b w 表示b比a大w
? a b 输出b比a大多少
#include<iostream>
using namespace std;
const int maxn = 100005;
int fa[maxn],val[maxn]; int find_(int x){
if(x != fa[x])
{
int t=fa[x];
fa[x]=find_(fa[x]);
val[x]+=val[t];
return fa[x];
}//路径压缩
return x;
}
void merge_(int a,int b,int c){
int fx,fy;
fx=find_(a);
fy=find_(b);
if(fx != fy)
{
fa[fx]=fy;
val[fx]=val[b]+c-val[a];
}
}
int main(){
int n,m;
while(cin>>n>>m&&n&&m){
char t;
int a,b,c;
for(int i=1;i<=m;i++)
fa[i]=i,val[i]=0;
while(m--){
cin>>t>>a>>b;
if(t == '!')
{
cin>>c;
merge_(a,b,c);
}
else
{
int fx,fy;
fx=find_(a),fy=find_(b);
if(fx != fy)
cout<<"UNKNOWN"<<endl;
else
cout<<val[a]-val[b]<<endl;
}
}
}
}
最新文章
- DockerCon 2016 – 微软带来了什么?
- Objective-C语法简记
- [翻译] 为什么Uber的数据库从Postgres 切换到 MySql
- AX7 VM can not starting
- 敏捷软件开发:原则、模式与实践——第8章 SRP:单一职责原则
- Azure 云助手正式发布
- Java-->;分割文件
- SVN版本控制与Visual Studio 2012的完美结合
- input type=";hidden"; js获取不到值(document.getelementbyid OR $(#).val())
- linux -->; gcc编译之路径搜索
- linux查看主板型号、CPU、显卡、硬盘等信息
- 通过C#发送自定义的html格式邮件
- HDU - 3917(朴素LIS + 最大流)
- try-with-resource机制的一个编译陷阱
- hdu2087 剪花布条
- PCIe 复位:Clod reset、warm reset、Hot reset、Function level reset
- JAVA-JSP内置对象之application对象
- Cannot find autoconf. Please check your autoconf installation and the $PHP_AUTOCONF environment variable. Then, rerun this scrip
- PyalgoTrade 技术组合计算(四)
- Python slice() 函数
热门文章
- 《Attention Augmented Convolutional Networks》注意力的神经网络
- IAR project build with command line
- asp.net core webapi处理Post请求中的request payload
- 面试题-linux基础
- Centos 7 修改日期和时间的命令
- 解决AndroidStudio引入Jar出现Unable to resolve dependency for &#39;:app@debug/compileClasspath
- Getting Started with XlsxWriter
- ssh:22端口拒绝服务
- nginx的autoindex,目录浏览,配置和美化,美观的xslt_stylesheet
- [转]Win2012的 IIS 503 错误