그냥 하는 노트와 메모장

분류 - [ 오일러 회로 ] 도로를 두 개 이상을 가지는 도시는 반드시 두 레스토랑을 갈 수 있어야 한다. 도로가 없거나 하나 이하의 경우는 생각하지 않기 때문에, 이 명제를 좀 변형 시켜보자. "도로를 두 개 이상을 가지는 도시에 대해 두 레스토랑을 보장하기 위해서 A 레스토랑이 있는 도로의 수를 Acnt, B 레스토랑이 있는 도로의 수를 Bcnt라고 할 때, Acnt는 Bcnt와 같아야 한다." 이것이 의미하는 바는 A와 B 레스토랑의 수를 같게 하면 명확하게 문제에서 원하는 도로를 배치할 수 있다. 따라서 A와 B를 진입/ 진출 간선처럼 생각하고, 항상 진입 간선 수=진출 간선 수가 같은 오일러 회로를 이용하여 문제를 해결한다. 단, 여기서 예외처리를 해줘야하는 점이 있다. 우선 Component가..

* Mike and Fish (http://codeforces.com/contest/547/problem/D) 뭐.. 문제 내용을 보면 생선을 싫어하는 곰, 마이크가 파란 생선과 빨간 생선을 2차원 좌표에 있는 바구니(?)에 하나씩 넣고자 한다. 또한 하나의 x축이나 y축에 대해 파란 생선 개수와 빨간 생선 개수의 차이가 1 이하로 만들기 위해 생선들을 각 좌표에 어떻게 배치시킬 것인지를 묻는 문제다. [분류 - Eulerian circuit/ Euler circult/ 오일러 회로/ 오일러 서킷] b clr[a] += (acc % 2 ? 1 : -1), clr[b] += (acc % 2 ? 1 : -1); x = a % 2 ? b : a; y = a % 2 ? a : b; ans[pool[make_pa..

* 오일러 회로 * 백준 온라인 저지 1. 오일러 회로 (https://www.acmicpc.net/problem/1199) 문제 이름부터가 오일러 회로다.. ㅎㅎ 가장 기본적인 오일러 회로를 따라가면 된다. 또한 무방향 그래프이기 때문에 방향성에 대해 확인할 필요가 없다. 기초적인 오일러 회로가 있는지 확인한 뒤, DFS를 돌리면 된다. 인접 행렬 코드 : #include #include using namespace std; int adj[1000][1000], n; vector c; void eulerianCircuit(int u) { for(int v=0;v= j) continue; addEdge(i, j, cap); } for (i = 0; i < n; i++) f &= (deg[i] && !(d..

* 오일러 서킷 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 시작점으로 돌아오기 때문에 오일러 서킷은 사이클임을 알 수 있다. * 오일러 경로 그래프의 모든 간선을 정확히 한 번씩 지나는 경로를 말한다. 시작점과 도착점이 다를뿐(오일러 경로는 사이클이 아니다), 나머지 속성은 오일러 서킷과 같다. * 오일러 서킷/경로 존재 조건 배제의 방식으로 접근한다. 반대로 오일러 서킷이 존재할 수 없는 그래프를 파악하면 된다. u = v의 경우는 오일러 서킷이고, u != v의 경우는 오일러 경로를 말한다. 1. Graph components가 두 개 이상 Components가 두 개 이상이면 한 번의 연산(사이클)이 절대로 모든 간선을 지날 수 없다. 2-1. (양/무방향 그래..