본문 바로가기

분류 전체보기327

BOJ 4196 - 도미노 (유니온 파인드로 저장) https://www.acmicpc.net/submit/4196/14605274 로그인 www.acmicpc.net 심심해서 유니온파인드로 scc를 저장해봤다. #include #include #include #include #define MAX 100001 using namespace std; int id, dfsn[MAX]; bool finished[MAX]; vector adj[MAX]; int sn[MAX],SN; int find(int a) { if (sn[a] == a) return a; return sn[a] = find(sn[a]); } void merge(int a, int b) { a = find(a); b = find(b); if (a == b) return; sn[a] = b; } .. 2019. 8. 19.
BOJ 2887 - 행성터널 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 www.acmicpc.net 특이하게 행성 간 간선으 비용이 min(x,y,z)이다. 모든 두 정점(n*n-1)에 대해서 최소값을 찾아가면서 간선을 두면 n이 1e.. 2019. 8. 19.
BOJ 10265 - MT (sAdj, 위상정렬, knapsack) https://www.acmicpc.net/problem/10265 10265번: MT 문제 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다. 재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래. 버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 www.acmicpc.net 간선을 다음과 같이 잡아준다. u : 난 v없으면 안가 // v->u scc끼리 묶은 그래프를 보면, 한 컴포넌트씩 살펴봤을 때 ind가 .. 2019. 8. 19.
냅색, knapsack https://www.acmicpc.net/problem/10265 10265번: MT 문제 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다. 재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래. 버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 www.acmicpc.net 이 문제의 기본 아이디어 작은 상자 n개에 사탕이 최소 mn개 최대 mx개 들어있을 때, 용량이 K인 큰 바구니에 최대 몇개의 사탕을 넣을.. 2019. 8. 19.

티스토리툴바