레야몬

1. 문제 한 양방향 그래프에서 어떤 예술가 한 쌍이 s지점에서 출발해서 g와 h 교차로 사이 도로를 지나 최단경로로 이동해 어떤 목적지로 도달한다고 할 때 어디로 가고 있을까? .- 1 - 테스트 케이스의 개수 \(T(1 \leq T \leq 100)\) - 1 - \(n, m, t(2 \leq n \leq 2,000, 1 \leq m \leq 50,000, 1\ \leq t \leq 100)\) 교차로, 도로 목적지 후보의 개수 - 2 - \(s, g, h(1 \leq s, g, h \leq n)\) s: 예술가의 출발지 \((g \neq h)\) - m개의 줄 - \(b, d(1 \leq a < b \leq n, 1 \leq d \leq 1,000)\) a와 b사이에 길이 d의 양방향 도로가 존재 ..

1. 문제 모든 판매원은 사수가 배정되며 한 회원당 단 한 명씩만 배정된다. 어떤 회원 A가 손해를 보면 그 회원의 모든 부사수도 같은 손해를 보고, 반대로 이익이 생기면 모든 부사수가 같은 이익을 본다. 승범이는 다음 두 종류의 명령을 처리하려 한다. 1 i w : 작은 i가 w만큼 이익/손해를 본다. 2 i : 직원 i의 현재 통장 잔액 출력 직원들은 빈 통장을 갖고 시작하며, 이익과 손해가 실시간으로 통장에 기록된다. 물론 통장 잔액은 음수일 수도 있다. -1- 판매원의 수 \(N(1 \leq N \leq 100,000)\), 명령의 수 \(M(1 \leq M \leq 100,000)\) 판매원들은 1~N번호로 매겨지며 승범이는 항상 1이다. -2- 1~N 사수가 순서대로 주어진다. 승범이는 사수가..

도시 왕복하기 2를 풀면서 같이 푼 문제라서 함께 풀이합니다. 1. 문제 도시 왕복하기 2: N개의 도시가 P개의 양방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 방문한 도시는 두 번 이상 방문할 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. 도시 왕복하기 1: N개의 도시가 P개의 방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 지난 길은 다시 지날 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. -1- \(N(3 \leq N \leq 400)\), \(P(1 \leq P \leq..

1. 문제 각 테스트케이스 첫째 줄 장소의 수 \(N(2 \leq N \leq 500)\)과 도로의 수 \(M(1 \leq M \leq 10^{4})\)가 주어짐. 0~N-1까지 장소의 번호가 매겨지는데 -2- 시작점 S, 도착점 D \((S \neq D, 0 \leq S, D V 도로는 최대 한 개이며 U->V는 V->U와 다르다. 입력의 마지막 줄에는 0이 두 개가 있다. 각 테스트케이스에 대해 거의 최단 경로 길이를 출력하며 없는 경우에는 -1을 출력하라 2. 재정의 최단 경로에 포함되는 도로 제외 최단 경로 3. 해결방법 - ..

2-SAT - 3이랑 2-SAT - 4랑 한꺼번에 풀어서 함께 풀이해보려고 한다. 1. 문제 변수의 개수 N과 절의 개수 M, 그리고 식 f가 주어졌을 때, 식 f를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하라. (있으면 그 해를 출력하라 ) \(N(1 \leq N \leq 10,000)\), \(M(1 \leq M \leq, 100,000)\) N과 M 절 \((1 \leq, \left|i \right|, \left|i \right| \leq N)\) i, j가 양수인 경우 xi, xj를 음수인 경우는 ㄱx-i, ㄱx-j를 나타낸다. 2*a-1, !xa -> 2*a으로 하고 !a -> b와 !b -> a를 그래프에 추가하자 ex) Vertex[2*a].push_back(2*b-1) 그..

2-SAT - 3이랑 2-SAT - 4랑 한꺼번에 풀어서 함께 풀이해보려고 한다. 1. 문제 변수의 개수 N과 절의 개수 M, 그리고 식 f가 주어졌을 때, 식 f를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하라. (있으면 그 해를 출력하라 ) \(N(1 \leq N \leq 10,000)\), \(M(1 \leq M \leq, 100,000)\) N과 M 절 \((1 \leq, \left|i \right|, \left|i \right| \leq N)\) i, j가 양수인 경우 xi, xj를 음수인 경우는 ㄱx-i, ㄱx-j를 나타낸다. 2*a-1, !xa -> 2*a으로 하고 !a -> b와 !b -> a를 그래프에 추가하자 ex) Vertex[2*a].push_back(2*b-1) 그..

#include #include #include #define FOR(i, k, N) for(int i=k; i> V >> E; FOR(i, 1, E) { int a, b; cin >> a >> b; Vertex[a].push_back(b); Vertex[b].push_back(a); } } int dfs(int no, int par) { discovered[no] = ++cnt; //발견된 순서(1부터 시작) int ret = discovered[no]; FOR(i, 1, Vertex[no].size()) { int next = Vertex[no][i-1]; //탐색할 노드 if(next == par) continue; if(!discovered[next]) { //탐색이 아직 되지 않았으면 int s..

#include #include #include #include #define MAX_V 10001 using namespace std; int V, E; //정점의 개수 V, 간선의 개수 E int vs[MAX_V], scc[MAX_V]; //visited 방문했는가? 이미 scc에 들어갔는가? int cnt; //bfs로 탐색된 순서 stack st; vector res, gr; //result, graph bool cmp(vector x, vector y) //벡터 정렬 { return x[0] > V >> E; gr.resize(V+1); for(int i=0; i> a >> b; gr[a].push_back(b); } } int dfs(int..