嗨,我正在做这个问题https://www.spoj.com/problems/BUGLIFE/在 SPOJ 上,但我得到了 WA,任何人都可以帮忙。这是我的代码。
我正在尝试使用集合来解决这个问题。我听说过使用二分图来解决这个问题,但我认为使用这种方法应该足够了,除非我的方法有问题。我已经尝试了很多测试用例,但我不知道我的代码在哪里失败了。
任何愿意提供帮助的人的额外测试用例:-
http://spojtoolkit.com/history/BUGLIFE
测试用例的预期输出
:-
http://spojtoolkit.com/test/BUGLIFE
示例输入:-
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4
示例输出:-
场景 #1:
发现可疑错误!
场景#2:
没有发现可疑的错误!
我的代码输出与预期输出相同。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int s = 0 ; s < t ; s++ ){
int bugs , inter; // Bugs and Interactions
cin >> bugs >> inter;
map<int,int> isDiscovered , male , female;
int bug1 , bug2;
vector<pair<int , int> > b; //stores pair of interactions
for(int i = 0 ; i < inter ; i++){
cin >> bug1 >> bug2;
b.push_back(make_pair(bug1,bug2));
}
sort(b.begin() , b.end());
bool ans = true;
for(int i = 0 ; i < b.size() ; i++){
bug1 = b[i].first;
bug2 = b[i].second;
//both not classified
if(isDiscovered.find(bug1) == isDiscovered.end() && isDiscovered.find(bug2) == isDiscovered.end()){
isDiscovered[bug1]++;
isDiscovered[bug2]++;
male[bug1]++;
female[bug2]++;
}
//one classified
if(isDiscovered.find(bug1) != isDiscovered.end() || isDiscovered.find(bug2) != isDiscovered.end()){
if(isDiscovered.find(bug1) == isDiscovered.end()){
//bug1 does not exist
isDiscovered[bug1]++;
if(male.find(bug2) == male.end()){
//bug2 is female
male[bug1]++;
}
else{
//bug2 is male
female[bug1]++;
}
}
else{
//bug2 does not exist
isDiscovered[bug2]++;
if(male.find(bug1) == male.end()){
//bug1 is female
male[bug2]++;
}else{
female[bug2]++;
}
}
}
//both classified
if(isDiscovered.find(bug1) != isDiscovered.end() && isDiscovered.find(bug2) != isDiscovered.end()){
if(male.find(bug1) != male.end() && male.find(bug2) != male.end()){
//both males
ans = false;
}
else if(female.find(bug1) != female.end() && female.find(bug2) != female.end()){
//both females
ans = false;
}
}
if(ans == false){
break;
}
}
cout << "Scenario #" << s+1 << ":" << endl;
if(ans == false){
cout << "Suspicious bugs found!" << endl;
}
else{
cout << "No suspicious bugs found!" << endl;
}
}
return 0;
}
最佳答案
如果两个 bug 都是新的,你无条件说第一个是雄性的,第二个是雌性的。不一定如此。我们只能假设他们是不同的性别,但还没有根据来指定性别。尝试
4 2
2 1
3 4
(与情况 2 相同,交换了第二对)。
关于c++ - 为什么我在 spoj 上获得 BUGLIFE 的 WA,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54685649/