HDU 3038 How Many Answers Are Wrong (并查集)
How Many Answers Are Wrong
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3404 Accepted Submission(s): 1310
FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin with, TT should write down a sequence of integers-_-!!(bored).
Then, FF can choose a continuous subsequence from it(for example the subsequence from the third to the fifth integer inclusively). After that, FF will ask TT what the sum of the subsequence he chose is. The next, TT will answer FF's question. Then, FF can redo this process. In the end, FF must work out the entire sequence of integers.
Boring~~Boring~~a very very boring game!!! TT doesn't want to play with FF at all. To punish FF, she often tells FF the wrong answers on purpose.
The bad boy is not a fool man. FF detects some answers are incompatible. Of course, these contradictions make it difficult to calculate the sequence.
However, TT is a nice and lovely girl. She doesn't have the heart to be hard on FF. To save time, she guarantees that the answers are all right if there is no logical mistakes indeed.
What's more, if FF finds an answer to be wrong, he will ignore it when judging next answers.
But there will be so many questions that poor FF can't make sure whether the current answer is right or wrong in a moment. So he decides to write a program to help him with this matter. The program will receive a series of questions from FF together with the answers FF has received from TT. The aim of this program is to find how many answers are wrong. Only by ignoring the wrong answers can FF work out the entire sequence of integers. Poor FF has no time to do this job. And now he is asking for your help~(Why asking trouble for himself~~Bad boy)
Line 2..M+1: Line i+1 contains three integer: Ai, Bi and Si. Means TT answered FF that the sum from Ai to Bi is Si. It's guaranteed that 0 < Ai <= Bi <= N.
You can assume that any sum of subsequence is fit in 32-bit integer.
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
using namespace std; const int SIZE = ;
int FATHER[SIZE],SUM[SIZE];
int N,M,ANS; void ini(void);
int find_father(int);
void unite(int,int,int);
int main(void)
{
int x,y,w; while(scanf("%d%d",&N,&M) != EOF)
{
ini();
while(M --)
{
scanf("%d%d%d",&x,&y,&w);
y ++;
unite(x,y,w);
}
printf("%d\n",ANS);
} return ;
} void ini(void)
{
ANS = ;
for(int i = ;i <= N + ;i ++)
{
FATHER[i] = i;
SUM[i] = ;
}
} int find_father(int n)
{
if(n == FATHER[n])
return n;
int temp = FATHER[n];
FATHER[n] = find_father(FATHER[n]);
SUM[n] = SUM[n] + SUM[temp];
return FATHER[n];
} void unite(int x,int y,int w)
{
int fx = find_father(x);
int fy = find_father(y); if(fx == fy)
{
if(SUM[x] - SUM[y] != w)
ANS ++;
return ;
} if(fx < fy)
{
FATHER[fx] = fy;
SUM[fx] = -SUM[x] + w + SUM[y];
}
else
{
FATHER[fy] = fx;
SUM[fy] = -SUM[y] - w + SUM[x];
}
}
最新文章
- PHP Fatal error: Call to undefined function mb_substr()
- ssm框架web.xml中filter配置问题
- Appium移动自动化测试(二)--安装Android开发环境
- HTML5 javascript CSS3 jQuery Mobile一些好用的网站
- ASP.NET静态页生成方法(模板替换)
- LLBL Gen Pro 5.0
- 网页class命名规范
- Robot Framework 使用1-环境配置及简单网站兼容性测试(转)
- jenkins构建基于gradle的springboot项目CI采坑(采用jar方式部署)
- crm 添加用户 编辑用户 公户和私户的展示,公户和私户的转化
- svn linux 服务器的搭建
- 让新版appium支持by_name定位
- mysql 开发进阶篇系列 3 SQL 优化(索引使用方法)
- 生产者、消费者模型---Queue类
- 范型方法 &; 范型参数 &; 范型返回值
- 把已经安装到C盘的软件完美移动到D盘
- tips: javascript 参数传递含有空格怎么办?
- 使用Intel IPT技术保护您的帐号安全
- Redis添加历史浏览记录
- HDU 6090 Rikka with Graph
热门文章
- C++ Vector 使用心得 [转]
- Mac OS增删环境变量
- Codeforces Round #215 (Div. 1) B. Sereja ans Anagrams 匹配
- 微信公共服务平台开发(.Net 的实现)11-------客服消息(定项消息推送 重要的OPENID)
- windows 支持curl命令
- Swift2.0 中的String(一):常用属性
- 文件写入文件分布式系统(asp.net C#)
- 自增锁预分配ID
- [原创]-CMD命令设置IP地址
- C#中String和string有什么区别