PS/Graph Theory(5)
-
BOJ 13361 : 최고인 대장장이 토르비욘
https://www.acmicpc.net/problem/13361 13361번: 최고인 대장장이 토르비욘 전성기 시절의 오버워치는 지구 상에서 가장 진보된 최첨단 무기를 보유했으며, 그 무기의 출처는 바로 토르비욘 린드홀름이라는 전무후무한 기술자의 작업장이었다. 하지만 이런 토르비욘에 www.acmicpc.net 여학 때 못 풀어서 1달 동안 힌트 + 생각해보고 푼 문제이다. 유니온 파인드로 서로 길이가 같은 것끼리 묶어주고, 이중 전체 변 길이의 합에서 서로 다른 (그룹에 있는 것들의 갯수)개의 길이를 빼면 된다. 풀이 자체는 아주 간다하지만, 정말이지 사람이 이걸 어캐 생각할 수 있는지 모르겠다. 코드
2021.11.15 -
BOJ 22344 : 그래프 균형 맞추기
https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 개인적으로 이번 KOI 고등 1번 난이도>>>>>>>이번 KOI 고등 2번 난이도라고 생각한다. 먼저 모든 정점의 가중치를 x+a나 -x+b로 표현 가능하다. 이를 통해 가중치의 합의 최소 = 절댓값 함수에서의 최솟값을 이용하면 된다. 이때 사이클이 있을때의 예외를 잘 처리해야 하는데, 사이클이 있을 때 어떤 임의의 두 인접한 정점에서 유일한 x값이 나오는 경우가 있다. 이를 주의하..
2021.08.01 -
BOJ 16562 : 친구비
16562번: 친구비 (acmicpc.net) 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 친구의 친구들은 모두 친구가 될 수 있다. 그렇다면 우리는 친한 부류끼리 묶어내서 그 부류 중 비용이 가장 최소인 것을 골라 더해주면 된다. 이는 Union-find로 하면 된다. 코드 djayy035/dj035_PS 코드저장소. Contribute to djayy035/dj035_PS development by creating an account on GitHub. gi..
2021.02.25 -
BOJ 10282 : 해킹
www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 우리는 여기서 모든 가능한 컴퓨터가 해킹되려면 컴퓨터가 해킹되는 경로 중에서 가장 시간이 최소인 경로를 찾아야 된다. 이는 다익스트라로 구할 수 있다. #include #define sanic ios_base::sync_with_stdio(0) #define MOD 1000000 using namespace std; typedef long long ll; typedef pair p; const ll MEM = 10..
2021.01.10 -
BOJ 15663 : N과 M (9)
이 문제는 n,m 범위가 엄청 작기에 백트래킹으러 풀 수 있다. 중복 수열 처리는 STL set의 중복 제거 특징을 이용하여 처리할 수 있다. #include #define sanic ios_base::sync_with_stdio(0); #define MEM 1002 #define f first #define s second #define pb push_back #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef pair pii; const ll MOD = 1e9+7; ll n,m; vector v,z; int vis[MEM]; set ans; void bt(int cur, int d){ if(d==m){..
2020.06.02