文档章节

A Bug's Life POJ - 2492

o
 osc_gccs85s0
发布于 07/12 11:42
字数 642
阅读 31
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

A Bug's Life

Background 
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs. 
Problem 
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.


Input

The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.

Output

The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.
 
题目:教授假设这种虫子有两种性别,且只有异性的虫子之间才有交流,每个虫子从1开始编号。接下来给出每对虫子之间的交流,问是不是只有异性之间才有交流。
思路:带权并查集板子题(不清楚带权并查集的点这里------>传送门)。同性权值为0,异性权值为1。
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <vector>
 6 #include <cmath>
 7 
 8 using namespace std;
 9 
10 #define ll long long
11 #define pb push_back
12 #define fi first
13 #define se second
14 
15 const int N = 2000 << 1;
16 struct node
17 {
18     int rt, v;
19 }fa[N];
20 
21 int Find(int x)
22 {
23     if(fa[x].rt == x) return x;
24     else{
25         int tmp = fa[x].rt;
26         fa[x].rt = Find(tmp);
27         fa[x].v = (fa[x].v + fa[tmp].v) % 2;
28         return fa[x].rt;
29     }
30 }
31 
32 bool Union(int x, int y)
33 {
34     int fax = Find(x);
35     int fay = Find(y);
36     if(fax != fay){
37         fa[fay].rt = fax;
38         fa[fay].v = (fa[x].v + 1 - fa[y].v) % 2;
39         return true;
40     }else{
41         if(0 == (fa[x].v + 1 - fa[y].v) % 2) return true;
42         else return false;
43     }
44 }
45 
46 void solve()
47 {   
48     int T;
49     scanf("%d", &T);
50     for(int _case = 1; _case <= T; ++_case){
51         int n, m;
52         scanf("%d%d", &n, &m);
53         for(int i = 0; i <= n; ++i){
54             fa[i].rt = i;
55             fa[i].v = 0;
56         }
57         vector<pair<int ,int > > info;
58         int x, y;
59         for(int i = 1; i <= m; ++i){
60             scanf("%d%d", &x, &y);
61             info.pb({x, y});
62         }
63 
64         int error = 0;
65         for(int i = 0; i < m; ++i){
66             x = info[i].fi;
67             y = info[i].se;
68             if(!Union(x, y)){
69                 error = 1;
70                 break;
71             }
72         }
73 
74         printf("Scenario #%d:\n", _case);
75         printf("%s\n\n", error == 1 ? "Suspicious bugs found!" : "No suspicious bugs found!");
76     }
77 }
78 
79 int main()
80 {
81 
82     solve();
83 
84     return 0;
85 }

 

o
粉丝 0
博文 76
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
基于Yii开发的博客--dlfblog

基于Yii 框架开发的博客!用于学习YII。 DLFBLOG 1.0 基于Yii 框架开发的博客! Quick start Clone the repo, git clone git://github.com/windsdeng/dlfblog.git, or download the latest r......

WindsDeng
2012/12/09
2.1K
0
轻量级校验框架--Jquery-Lweight-validate

jquery-Lweight-Validate :轻量级校验框架。之所以这么称呼它。原因很简单,与其他校验框架相比,次框架没有太多的JS代码在你的HTML中,仅仅一行,其他所有的校验属性,均通 过框架中自定义...

德古拉-大猫
2013/05/05
2.8K
3
移动端组件库--Global Mobile UI

GMU(Global Mobile UI)是百度前端通用组开发的移动端组件库,具有代码体积小、简单、易用等特点,组件内部处理了很多移动端的bug,覆盖机型广,能大大减少开发交互型组件的工作量,非常适合...

匿名
2013/06/03
9.8K
1
jquery对象/标签映射扩展--NickName

jquery对象/标签映射扩展-NickName OTM是什么 以往把这样的一个json对象 var data = {}; data.UserId = "8888"; data.UserName = "赵六"; data.School="湖北工业大学"; data.schoolNo=100002......

知鸣
2013/06/13
1K
0
monodevelop2.6beta1发布

http://monodevelop.com/,最近在用monodevelop做mvc2的开发,感觉不错,有些方面强过vs2008,不过bug也不少。

mythad
2011/03/02
687
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在IntelliJ中永久启用行号? - How can I permanently enable line numbers in IntelliJ?

问题: 如何在IntelliJ IDEA中永久启用行号? 解决方案: 参考一: https://stackoom.com/question/3Zn/如何在IntelliJ中永久启用行号 参考二: https://oldbug.net/q/3Zn/How-can-I-permane...

法国红酒甜
24分钟前
3
0
Docker镜像加速

vim /etc/docker/daemon.json # 将"registry-mirrors": ["https://......com"] (对应自己的加速地址)复制到文件中 # 重新加载文件和重启dockersudo systemctl daemon-reloadsudo syst......

codeccb
36分钟前
12
0
Android Studio使用lombok

参考:https://github.com/mplushnikov/lombok-intellij-plugin 使用@Setter/@Getter时,刚开始在Structure的函数列表里没有生成响应的函数,且调用set/get的地方也报红,但编译OK。 按网上的...

大熊猫
36分钟前
7
0
Stream数据流

Stream类基础操作 从JDK1.8开始提供了java.yitl.stream数据流的开发板,而Stream就是这个包中提供的一个接口,这个接口主要是通过函数式编程结构实现集合数据的分析,所以在Collection接口张...

哼着我的小调调
41分钟前
13
0
在视图控制器之间传递数据 - Passing Data between View Controllers

问题: I'm new to iOS and Objective-C and the whole MVC paradigm and I'm stuck with the following: 我是iOS和Objective-C以及整个MVC范例的新手,但我坚持以下几点: I have a view th......

fyin1314
54分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部