博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Never Wait for Weights(带权并查集+路径压缩)
阅读量:5129 次
发布时间:2019-06-13

本文共 879 字,大约阅读时间需要 2 分钟。

题目链接:

!a b w 表示b比a大w

?  a b  输出b比a大多少

#include
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"<

  

 

转载于:https://www.cnblogs.com/LLLAIH/p/10731556.html

你可能感兴趣的文章
想做移动开发,先看看别人怎么做
查看>>
Eclipse相关集锦
查看>>
虚拟化架构中小型机构通用虚拟化架构
查看>>
继承条款effecitve c++ 条款41-45
查看>>
Java泛型的基本使用
查看>>
1076 Wifi密码 (15 分)
查看>>
noip模拟赛 党
查看>>
bzoj2038 [2009国家集训队]小Z的袜子(hose)
查看>>
Java反射机制及其Class类浅析
查看>>
Postman-----如何导入和导出
查看>>
移动设备显示尺寸大全 CSS3媒体查询
查看>>
图片等比例缩放及图片上下剧中
查看>>
【转载】Linux screen 命令详解
查看>>
background-clip,background-origin
查看>>
Android 高级UI设计笔记12:ImageSwitcher图片切换器
查看>>
【Linux】ping命令详解
查看>>
对团队成员公开感谢博客
查看>>
java学习第三天
查看>>
python目录
查看>>
django+uwsgi+nginx+sqlite3部署+screen
查看>>