题意:

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;
}

最新文章

  1. [C#] 走进异步编程的世界 - 开始接触 async/await
  2. 本机ip+端口不能访问web server,外部却可以访问
  3. javaScript事件(四)event的公共成员(属性和方法)
  4. C#之匿名类型与隐式局部变量
  5. 剑指Offer22 判断数组是否为某二叉搜索树的后序遍历
  6. oracle dblink 配置两个ip
  7. C#模拟POST提交表单(二)--HttpWebRequest以及HttpWebResponse
  8. knn算法详解
  9. 【HDU - 5790 】Prefix(主席树+Trie树)
  10. python的paramiko模块-远程登录linux主机并操作
  11. uva-10700-贪心
  12. 使用redis 处理高并发场景
  13. Uploading File using Ajax and receiving binary data in Asp.net (C#)[转]
  14. The J-Link hardware debugging Eclipse plug-in
  15. JS 获取当前日期的前一天日期(年月日格式)
  16. 网络电台-SHOUTcast
  17. DRF频率、分页、解析器、渲染器
  18. thinkphp5 隐藏入口和支持pathinfo
  19. Spring的消息 Java Message Service (JMS)
  20. servlet ; basepath ; sendredirected ;

热门文章

  1. Dapr实战(一) 基础概念与环境搭建
  2. final关键字在PHP中的使用
  3. 关于python如何构造测试数据
  4. HTML 网页开发、CSS 基础语法——二.互联网原理
  5. 鸿蒙内核源码分析(源码注释篇) | 鸿蒙必定成功,也必然成功 | 百篇博客分析OpenHarmony源码 | v13.02
  6. windows下将Anaconda移位置(C盘转移至D盘)
  7. java/ kotlin下的单例模式
  8. linux下nginx编译安装、版本信息修改
  9. 洛谷3809 SA模板 后缀数组学习笔记(复习)
  10. 洛谷3348 大森林 (LCT + 虚点 + 树上差分)