레이블이 Algorithm인 게시물을 표시합니다. 모든 게시물 표시
레이블이 Algorithm인 게시물을 표시합니다. 모든 게시물 표시

2020년 7월 1일 수요일

알고스팟 - PICNIC

이거 종만 아재가 완전탐색으로 풀라고 던진 문제임.

어차피 선택 문제이므로 노드를 탐색하는 순서가 하나면 됨.

예를들어서 연결된 노드의 숫자가 적은 노드부터, 혹은 많은 노드부터 순서대로 조사하는 거임.

상식적으로 적은 노드부터 하는게 더 빠를거라고 생각될 거임.

실제로 알고스팟 결과는 2배 정도 차이남.




#include <iostream>
#include <vector>
#include <algorithm>
//#include "Random.h" class Class
{
public:
Class() = default;
~Class() = default; friend std::istream& operator>>(std::istream& in, Class& rhs)
{
in >> rhs.nStudent >> rhs.nFriend; for (int i = 0; i < rhs.nFriend; i++)
{
std::pair<int, int> tmp;
in >> tmp.first >> tmp.second;
rhs.m_friends.emplace_back(tmp);
} return in;
} std::vector<int> Init_Code_Count(std::vector<std::pair<int, int>> friend_relations)
{
std::vector<int> code_count(nStudent); for (const auto& f : friend_relations)
{
code_count[f.first]++;
code_count[f.second]++;
} for (auto& c : code_count)
if (c <= 0)
c = 99999; return code_count;
} void Do()
{
std::cout << Delete_Til(std::make_pair(-1, -1), Init_Code_Count(m_friends), m_friends) << std::endl;;
} int Delete_Til(std::pair<int, int> choosen, std::vector<int> code_count, std::vector<std::pair<int, int>> friend_relations)
{
int result = 0; if (choosen.first != -1)
{
code_count[choosen.first] = 999999;
code_count[choosen.second] = 999999; for (auto iter = friend_relations.begin(); iter != friend_relations.end();)
{
if (iter->first == choosen.first || iter->second == choosen.first ||
iter->first == choosen.second || iter->second == choosen.second)
iter = friend_relations.erase(iter);
else
iter++;
}
} if (friend_relations.size() <= 0)
{
for (const auto& c : code_count)
{
if (c != 999999)
return 0;
}
return 1;
} auto _min = *std::min_element(code_count.begin(), code_count.end());
std::vector<int> _student_with_min_friends;
for (int i = 0; i < nStudent; i++)
if (code_count[i] == _min)
{
_student_with_min_friends.push_back(i);
break;
}
auto a = Find(_student_with_min_friends, friend_relations); for (auto s : Find(_student_with_min_friends, friend_relations))
{
result += Delete_Til(s, code_count, friend_relations);
} return result;
} std::vector<std::pair<int, int>> Find(std::vector<int>& student_with_min_friends, std::vector<std::pair<int, int>>& friend_relations)
{
std::vector<std::pair<int, int>> results; for (auto f : friend_relations)
{
bool isChoosen = false;
for (auto s : student_with_min_friends)
{
if ((f.first == s || f.second == s) && !isChoosen)
{
results.emplace_back(f);
isChoosen = true;
}
}
} return results;
} private:
int nStudent;
int nFriend;
std::vector<std::pair<int, int>> m_friends; }; int main()
{
int nCase;
std::vector<Class> classes;
std::cin >> nCase;
for (int i = 0; i < nCase; i++)
{
Class cls;
std::cin >> cls;
classes.emplace_back(cls);
}
for (auto cls : classes)
{
cls.Do();
}
}

List