Zjnu Stadium
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 989 Accepted Submission(s): 388
Problem Description
In 12th Zhejiang College Students Games 2007, there was a new stadium built in Zhejiang Normal University. It was a modern stadium which could hold thousands of people. The audience Seats made a circle. The total number of columns were 300 numbered 1--300, counted clockwise, we assume the number of rows were infinite.
These days, Busoniya want to hold a large-scale theatrical performance in this stadium. There will be N people go there numbered 1--N. Busoniya has Reserved several seats. To make it funny, he makes M requests for these seats: A B X, which means people numbered B must seat clockwise X distance from people numbered A. For example: A is in column 4th and X is 2, then B must in column 6th (6=4+2).
Now your task is to judge weather the request is correct or not. The rule of your judgement is easy: when a new request has conflicts against the foregoing ones then we define it as incorrect, otherwise it is correct. Please find out all the incorrect requests and count them as R.
These days, Busoniya want to hold a large-scale theatrical performance in this stadium. There will be N people go there numbered 1--N. Busoniya has Reserved several seats. To make it funny, he makes M requests for these seats: A B X, which means people numbered B must seat clockwise X distance from people numbered A. For example: A is in column 4th and X is 2, then B must in column 6th (6=4+2).
Now your task is to judge weather the request is correct or not. The rule of your judgement is easy: when a new request has conflicts against the foregoing ones then we define it as incorrect, otherwise it is correct. Please find out all the incorrect requests and count them as R.
Input
There are many test cases:
For every case:
The first line has two integer N(1<=N<=50,000), M(0<=M<=100,000),separated by a space.
Then M lines follow, each line has 3 integer A(1<=A<=N), B(1<=B<=N), X(0<=X<300) (A!=B), separated by a space.
For every case:
The first line has two integer N(1<=N<=50,000), M(0<=M<=100,000),separated by a space.
Then M lines follow, each line has 3 integer A(1<=A<=N), B(1<=B<=N), X(0<=X<300) (A!=B), separated by a space.
Output
For every case:
Output R, represents the number of incorrect request.
Output R, represents the number of incorrect request.
Sample Input
10 10
1 2 150
3 4 200
1 5 270
2 6 200
6 5 80
4 7 150
8 9 100
4 8 50
1 7 100
9 2 100
Sample Output
2
Hint
Hint: (PS: the 5th and 10th requests are incorrect)题意:
给出N(1到50000)个人和M(0到1000000)条关系。每条关系有A,B,W,代表A位置与B位置有W个距离,A在前,B在后,全部位置最多有300个。给出M种关系中,判断错误的位置关系有几条。输出错误的信息数。
思路:
带权并查集。权值记录A到B的距离,如果判断A和B不在同一个根节点,则合并;如果在同一个根节点则查询判断是否为错误信息,是则ans增加1。
AC:
#include<stdio.h> #define max 50000+5 int root[max],re[max]; int find(int a) { if(root[a]==a) return a; int r=find(root[a]); re[a]=(re[a]+re[root[a]])%300; root[a]=r; return r; } int main() { int n,m,ans; while(scanf("%d%d",&n,&m)!=EOF) { ans=0; for(int i=1;i<=n;i++) { root[i]=i; re[i]=0; } while(m--) { int a,b,w; int fa,fb; scanf("%d%d%d",&a,&b,&w); fa=find(a); fb=find(b); if(fa!=fb) { root[fa]=fb; re[fa]=(re[b]+w-re[a]+300)%300; } else { if((re[a]-re[b]+300)%300!=w) ans++; } } printf("%d\n",ans); } return 0; }
总结:
WA了一次,因为输入要用EOF输入(There are many test cases)。
相关推荐
zjnu宽带连接,移动连接
该软件是一个类似,系统记事本的一个工具,
123
软件工程课程设计指导书目录 一、软件工程课程设计指导书选用范围 二、课程设计基本目的与可能收获 三、网站开发项目1(网上书店My-eBookStore)介绍 网站开发项目2(创业网站My-eCompany)介绍 ...
浙师地图 为浙师大学生提供便捷的服务~ 功能简介PAD图
很不错的东东,一份让你意想不到的惊喜啊,呵呵呵呵呵呵呵呵呵呵……
算法分析与设计-大型实验报告样本 五、参考资源 在网络上有很多论坛,欢迎大家参考。著名的有: 浙江大学在线论坛,衡阳市第八中学信息学奥赛论坛,杭州电子科技大学...浙江师范大学ACM/ICPC论坛:http://acm.zjnu.cn/
TreeLib将作者的需求放在第一位,并重视进行大量审查。 如何贡献 我们欢迎您参与这个项目。 您的参与不必以贡献代码的形式进行。 您可以在想法,建议,文档等方面为我们提供帮助。 您需要成为Lan实验室的受邀成员...
浙江师范大学(ZJNU): 浙江工商(ZJGSU): 宁波理工(NIT): 上海: 华东师范大学(ECNU): 华东理工大学(ECUST): 同济大学(TJU): 江苏: 南京航空航天大学: 福建: 福州大学(FZU): 厦门大学(XMU)...
QCDLD_latest.exe