hdu 3038 How Many Answers Are Wrong(并查集)
2024-10-19 13:23:49
题意:
N和M。有N个数。
M个回答:ai, bi, si。代表:sum(ai...bi)=si。如果这个回答和之前的冲突,则这个回答是假的。
问:M个回答中有几个是错误的。
思路:
如果知道sum(ai...bi)=si。假设下一个是sum(ai,ci)=sj。则sum(ai,ci)肯定也知道了。这很符合并查集的结构。
*:画个图。
代码:
int n,m;
int fa[200005];
int sum[200005]; int findFa(int x){
if(fa[x]==x){
return fa[x];
}
int t=fa[x];
fa[x]=findFa(fa[x]);
sum[x]+=sum[t];
return fa[x];
} int main(){ while(scanf("%d%d",&n,&m)!=EOF){
rep(i,0,n){
fa[i]=i;
sum[i]=0;
}
int ans=0;
while(m--){
int A,B,S;
scanf("%d%d%d",&A,&B,&S);
int fA=findFa(A-1);
int fB=findFa(B);
if(fA!=fB){
fa[fB]=fA;
sum[fB]+=(sum[A-1]+S-sum[B]);
}else{
if(sum[A-1]+S!=sum[B]){
++ans;
}
}
} printf("%d\n",ans);
} return 0;
}
最新文章
- [C#] 走进异步编程的世界 - 开始接触 async/await
- 本机ip+端口不能访问web server,外部却可以访问
- javaScript事件(四)event的公共成员(属性和方法)
- C#之匿名类型与隐式局部变量
- 剑指Offer22 判断数组是否为某二叉搜索树的后序遍历
- oracle dblink 配置两个ip
- C#模拟POST提交表单(二)--HttpWebRequest以及HttpWebResponse
- knn算法详解
- 【HDU - 5790 】Prefix(主席树+Trie树)
- python的paramiko模块-远程登录linux主机并操作
- uva-10700-贪心
- 使用redis 处理高并发场景
- Uploading File using Ajax and receiving binary data in Asp.net (C#)[转]
- The J-Link hardware debugging Eclipse plug-in
- JS 获取当前日期的前一天日期(年月日格式)
- 网络电台-SHOUTcast
- DRF频率、分页、解析器、渲染器
- thinkphp5 隐藏入口和支持pathinfo
- Spring的消息 Java Message Service (JMS)
- servlet ; basepath ; sendredirected ;
热门文章
- Dapr实战(一) 基础概念与环境搭建
- final关键字在PHP中的使用
- 关于python如何构造测试数据
- HTML 网页开发、CSS 基础语法——二.互联网原理
- 鸿蒙内核源码分析(源码注释篇) | 鸿蒙必定成功,也必然成功 | 百篇博客分析OpenHarmony源码 | v13.02
- windows下将Anaconda移位置(C盘转移至D盘)
- java/ kotlin下的单例模式
- linux下nginx编译安装、版本信息修改
- 洛谷3809 SA模板 后缀数组学习笔记(复习)
- 洛谷3348 大森林 (LCT + 虚点 + 树上差分)