cho.sh

문제

문제를 고르고 내장 에디터에서 풀이를 작성해 보시기 바랍니다. 채점기가 실제 테스트 케이스로 코드를 바로 검증하고, 아카이브의 문제들도 자유롭게 둘러볼 수 있습니다.

전체 결과문제 366개
제목난이도유형정답자시간 제한메모리 제한채점
최소 중앙값 스패닝 트리노드 수가 짝수인 연결 그래프의 스패닝 트리 가운데 간선 비용 중앙값의 최솟값을 구합니다.보통7최소 신장 트리유니온 파인드+1아직 제출이 없습니다8초256 MB채점 가능
다리 건설 계획A사 간선 k개와 B사 간선을 합쳐 n-1개로 모든 섬을 잇는 가장 싼 연결 계획을 구합니다.보통7최소 신장 트리이분 탐색아직 제출이 없습니다1초256 MB채점 가능
어색한 모임내부 친밀도의 최댓값이 외부와의 모든 친밀도보다 작은 부분집합 개수를 셉니다.보통7최소 신장 트리유니온 파인드+1아직 제출이 없습니다5초256 MB채점 가능
수족관R행 C열 격자의 대각선 벽을 가장 적은 비용으로 허물어 전체를 하나의 구역으로 만듭니다.보통7최소 신장 트리유니온 파인드+1아직 제출이 없습니다3초256 MB채점 가능
울타리 걷어내기인접한 구역 사이 울타리를 뜯어 모든 구역이 이어지도록 하고 뜯어낸 길이 합을 가장 작게 만듭니다.보통7최소 신장 트리그리디+1아직 제출이 없습니다2초512 MB채점 가능
울타리에 갇힌 소 (Gold)격자로 나뉜 목장의 모든 구역이 통하도록 제거하는 울타리 길이 합을 최소화합니다.보통7최소 신장 트리그리디+1아직 제출이 없습니다2초512 MB채점 가능
도시들가중 무방향 그래프에서 k개의 중요한 도시(k는 최대 10)가 모두 한 연결 요소에 속하도록 간선을 골라 최소 비용을 구한다.보통7최소 신장 트리동적 계획법+2아직 제출이 없습니다4초256 MB채점 가능
돌다리 놓기가중치가 있는 연결 무방향 그래프에서 간선을 임의 순서로 지을 때, 섬 1과 섬 N이 연결되는 시점의 최솟값과 최댓값을 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다2초128 MB채점 가능
분단의 슬픔고정된 소속을 지키면서 N명을 두 진영으로 나눠 진영이 다른 쌍의 가중치 합을 최소로 하고, 그중 A 진영이 가장 작은 해를 출력한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB채점 가능
수도 선정각 도시 i가 R[i]와 도로로 이어진 연결 다중 그래프에서, 임의의 두 도시 사이 모든 단순 경로가 지나는 도시가 생기도록 인접한 도시를 최소 횟수로 합친다.보통7그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
잭 에드먼즈맨해튼 거리 도로를 n-1개 이하로 지어, 출발점에서 모든 지점을 돌아오는 최단 왕복 경로의 길이를 구한다.보통7최소 신장 트리그래프+1아직 제출이 없습니다2초256 MB채점 가능
트럭가중치가 있는 무방향 그래프에서 두 정점 사이 경로의 최소 간선 가중치를 최대로 하는 값을 S개의 질의에 대해 각각 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
도로 건설가중치가 있는 무방향 그래프가 주어질 때, 모든 도시가 서로 연결되고 수도에서 각 도시까지의 최단 거리가 원래와 같은 부분 그래프를 만들 때 드는 최소 건설 비용을 구한다.보통7그래프최단 경로+2아직 제출이 없습니다8초512 MB채점 가능
명제 증명N개의 명제가 서로를 함의하도록 방향 간선을 골라, 선택한 증명 난이도의 최댓값과 최솟값 차이를 최소로 만든다.보통7그래프투 포인터+2아직 제출이 없습니다2초512 MB채점 가능
학급비 낭비하기각 친구는 뽀끄뽀끼 색과 꼬끼꼬끼 모델에 대해 반대 방향의 요구 하나를 제시하며, 구매 여부를 정해 만족하는 친구 수를 최대로 하고 나머지를 출력한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
물건 배달가중치가 있는 방향 그래프와 고객 정점들이 주어질 때, 각 고객을 최단 시간에 방문하도록 트럭 경로를 배정하는 최소 대수를 구한다.보통7그래프최단 경로+2아직 제출이 없습니다5초512 MB채점 가능
정복자도시 1에서 시작해 모든 도시를 정복하되, k번째로 정복하는 도시의 비용은 간선 비용에 (k-1)*t를 더한 값이며, 총비용을 최소로 만든다.보통7최소 신장 트리그리디+2아직 제출이 없습니다2초256 MB채점 가능
몇 개를 지워야 행복할까각 간선이 어떤 최소 신장 트리에 속하도록 만들기 위해 지워야 할 간선 수의 최솟값을 구해 모두 더한다.보통7최소 신장 트리그래프+2아직 제출이 없습니다0.5초512 MB채점 가능
dgeu-learning가중치가 있는 연결 그래프에서 두 정점 사이 병목 경로의 최댓값을 묻는 질의에 답한다.보통7최소 신장 트리유니온 파인드+2아직 제출이 없습니다4초512 MB채점 가능
T-net직선 위의 각 기지국에 두 가지 반지름 중 하나를 골라 네트워크를 연결하면서 반지름 합을 최소로 만든다.보통7그리디정렬+2아직 제출이 없습니다2초512 MB지문만 제공
Enlarge CirclesN개의 점 각각을 중심으로 하는 원을 반지름 0도 허용하면서 서로 겹치지 않고 접촉만 하도록 배치해 둘레 합의 최댓값을 구한다.보통7기하그래프+2아직 제출이 없습니다2초512 MB지문만 제공
레드 블루 스패닝 트리 2빨간색과 파란색 간선으로 이루어진 연결 무향 그래프에서 파란 간선을 정확히 k개 사용하는 신장 트리가 존재하는지 판별하고, 존재하면 하나를 출력한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
그리드 네트워크각 꼭짓점에 인접한 간선들의 비용이 서로 다른 1~4의 값을 갖는 격자 그래프에서 최소 신장 트리의 비용을 구한다.보통7최소 신장 트리그래프+2아직 제출이 없습니다2초256 MB채점 가능
We Need More Managers!길이 n인 서로 다른 이진 문자열 m개가 주어질 때, 모든 정점을 포함하는 루트 트리를 만들어 부모와 자식 사이 해밍 거리의 합이 최소가 되도록 해야 한다.보통7최소 신장 트리그래프+2아직 제출이 없습니다20초512 MB지문만 제공
King's Roads도시 i와 j를 잇는 도로의 비용이 a_i + a_j이고 합이 M 이상이면 M을 돌려받을 때, 모든 도시를 연결하는 최소 비용을 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다2초256 MB지문만 제공
Circles반지름 0에서 같은 속도로 자라는 원들이 다른 원과 닿으면 멈출 때, 최종적으로 모든 원이 차지하는 넓이의 합을 구한다.보통7기하최소 신장 트리+2아직 제출이 없습니다8초1024 MB지문만 제공
Optimization for UltraNet케이블을 제거해 네트워크 병목을 최대로 하고 그다음 전체 대역폭 합을 최소로 하는 신장 트리를 만든 뒤, 모든 도시 쌍의 경로 병목 합을 구한다.보통7최소 신장 트리그래프+2아직 제출이 없습니다3초1024 MB지문만 제공
Generators도시들이 원형으로 배치되어 있고 각 간선에 설치 비용이 주어질 때, 일부 도시에만 지을 수 있는 발전소 비용을 고려해 모든 도시에 전력을 공급하는 최소 비용을 구한다.보통7동적 계획법그래프+2아직 제출이 없습니다2초512 MB지문만 제공
완전그래프의 최소 스패닝 트리정점 값과 상수로 계산한 간선 가중치를 가진 완전그래프에서 최소 신장 트리의 가중치 합을 구한다.보통7최소 신장 트리그래프+2아직 제출이 없습니다5초16 MB지문만 제공
PO-arkiveringN개의 풀이에 대해 각 풀이의 크기와 두 풀이 사이의 diff 비용이 주어질 때, 모든 풀이를 복원할 수 있도록 저장해야 하는 최소 바이트 수를 구한다.보통7그래프최소 신장 트리+1아직 제출이 없습니다1초1024 MB지문만 제공
Slow Down연결된 가중 무방향 그래프에서 간선 가중치를 늘려 정점 1에서 N까지의 최단 경로 길이를 최소 비용으로 1 이상 증가시키는 문제입니다.보통7그래프최단 경로+2아직 제출이 없습니다1초512 MB지문만 제공
Sending Blessings정점 N개와 간선 N개로 이루어진 연결 그래프에서 Q개의 질의마다 두 도시 사이 경로의 최대 병목 용량을 구한다.보통7그래프최소 신장 트리+1아직 제출이 없습니다2초512 MB지문만 제공
Trail MaintenanceN개 정점 그래프에 매주 간선 하나씩 추가될 때마다 최소 신장 트리의 총 길이를 출력하고, 연결되지 않으면 -1을 출력한다.보통7최소 신장 트리유니온 파인드+2아직 제출이 없습니다1초512 MB지문만 제공
Surround the Castle각 칸의 비용이 주어질 때 성을 외부와 차단하도록 해자 칸을 골라 총비용을 최소로 만든다.보통7그래프최단 경로+1아직 제출이 없습니다2초512 MB지문만 제공
marukaiten×n 격자에서 각 칸에 원을 쓰거나 지우는 비용이 주어질 때, 모든 행과 열에 원이 정확히 하나씩 있도록 만드는 최소 비용과 그 연산 목록을 구한다.보통7최소 신장 트리그래프+1아직 제출이 없습니다8초512 MB지문만 제공
Save your cats말뚝 사이에 서로 교차하지 않는 울타리로 이루어진 평면 그래프가 주어질 때, 닫힌 영역이 남지 않도록 부수어야 하는 울타리 길이의 최솟값을 구합니다.보통7그래프최소 신장 트리+2아직 제출이 없습니다8초512 MB지문만 제공
Building Bridges원형 섬들과 기존 다리가 주어질 때, 다리가 섬이나 다른 다리를 가로지르지 않으면서 모든 섬을 연결하는 새 다리의 최소 총 길이를 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다8초512 MB지문만 제공
방탈출N개의 방 그래프에서 워프(가중 간선)와 방마다의 비상탈출구를 골라 모든 방이 출구에 도달하도록 하면서 총 설치 시간을 최소로 만든다.보통7최소 신장 트리그래프+2아직 제출이 없습니다2초1024 MB지문만 제공
Cards Game카드 두 장을 골라 한 장의 빨간 수와 다른 장의 파란 수를 XOR한 값을 더한 뒤 한 장을 되돌리는 과정을 반복할 때, 카드 한 장이 남을 때까지 얻을 수 있는 최소 합을 구한다.보통7최소 신장 트리그래프+2아직 제출이 없습니다20초1024 MB지문만 제공
シムロード (SimRoad) 14방향 격자에서 모든 마을이 서로 이동할 수 있도록 최소한의 풀을 베고, 그 결과 지도를 출력한다.보통7그래프최소 신장 트리+1아직 제출이 없습니다1초1024 MB지문만 제공
シムロード (SimRoad) 4출력 전용 문제로, 모든 집락이 연결되도록 최소 개수의 풀을 벤 결과 상태를 만든다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
シムロード (SimRoad) 5모든 집락이 서로 이동할 수 있도록 풀을 벨 칸을 골라 비용을 최소로 하고, 그 결과 격자를 출력한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
히히 못가같은 알파벳끼리 연결된 영역으로 나뉜 N×N 격자에서 왼쪽 위와 오른쪽 아래를 분리하기 위해 사야 하는 최소 칸 수를 구한다.보통7그래프DFS+1아직 제출이 없습니다1.5초1024 MB지문만 제공
Moo Networky가 0에서 10 사이인 최대 100000개 점이 주어질 때, 제곱 유클리드 거리를 간선 가중치로 하는 최소 신장 트리의 비용을 구한다.보통7최소 신장 트리그래프+1아직 제출이 없습니다4초1024 MB지문만 제공
Edges, Colors and MST1부터 M까지의 순열을 간선 가중치로 부여해 최소 신장 트리가 주어진 빨간 신장 트리와 정확히 일치하도록 만들되, 수열을 사전순으로 가장 작게 만든다.보통7최소 신장 트리그리디+2아직 제출이 없습니다2초1024 MB지문만 제공
Planning Railroad Discontinuation동일한 지하철망을 가진 도시들이 고리 모양으로 놓여 있고 인접 도시가 같은 번호의 역에서 연결될 때, 모든 역을 연결하는 최소 유지비를 구한다.보통7그래프최소 신장 트리+1아직 제출이 없습니다5초1024 MB지문만 제공
MMST모든 간선 가중치가 서로 다른 연결 무향 그래프에서, 가중치 합이 최소 신장 트리와 최대 신장 트리 어느 쪽과도 다른 신장 트리를 찾아 출력하거나, 불가능하면 NO를 출력한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
RymdpatrullenN개의 기지에서 (D 합) 곱하기 (L 합)을 최소로 하는 신장 트리를 골라, 두 합과 간선 목록을 출력한다.보통7최소 신장 트리그래프+2아직 제출이 없습니다1초1024 MB지문만 제공
크루스칼 알고리즘크루스칼 알고리즘으로 최소 신장 트리를 만들 때 가능한 간선 추가 순서와 집합의 경우의 수를 998244353으로 나눈 나머지를 구한다.보통7최소 신장 트리유니온 파인드+2아직 제출이 없습니다2초1024 MB지문만 제공
Toll Roads두 도시 사이를 잇는 경로의 최대 통행료를 최소로 하는 값을 구하고, 그 값 이하의 도로만 써서 출발 도시에서 갈 수 있는 도시 수를 센다.보통7최소 신장 트리유니온 파인드+2아직 제출이 없습니다3초1024 MB지문만 제공
LazyC1 비용 합이 최소인 신장 트리 중에서 C1*C2 이익의 합이 최대가 되는 간선 N-1개를 골라 입력 순서대로 출력한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
체인소 맨N×M 격자와 목표 모양이 주어질 때, 작업 영역을 가로지르는 반직선 절단은 F, 길이 l의 선분 절단은 l의 힘이 들며, 목표 모양을 분리하는 최소 힘을 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
Bounded Spanning Tree주어진 그래프에서 처음 n-1개의 간선이 최소 신장 트리를 이루도록, 각 간선의 허용 구간을 지키며 1부터 m까지 서로 다른 가중치를 배정하는 문제이다.보통7최소 신장 트리그리디+2아직 제출이 없습니다2.5초1024 MB지문만 제공
치즈각 상점이 두 종류의 치즈를 정해진 가격에 묶어 팔고 두 종류 목록이 모두 순열일 때, N가지 치즈를 모두 사는 최소 비용을 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
Eroding Pillars기둥 좌표가 최대 1000개 주어질 때, 로봇이 원점에서 임의의 기둥 하나를 방문하고 같은 기둥을 두 번 밟지 않으면서 돌아올 수 있게 하는 최소 점프 거리를 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다10초1024 MB지문만 제공
ИсторияN, M, S, R이 주어질 때, 간선 가중치가 1 이상 R 이하이고 최소 신장 트리의 가중치가 S인 연결 단순 무방향 그래프를 구성하거나 불가능함을 판별한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
Прыгать!신장 트리를 골라 일부 간선을 c배 비용의 고속도로로 지정해, 예산 k 안에서 고속도로 수를 최대로 만든다.보통7그래프최소 신장 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
Дороги유료 도로와 무료 도로가 섞인 연결 다중 그래프에서 유료 도로를 정확히 k개 포함하는 신장 트리를 찾아 출력하거나, 불가능하면 -1을 출력한다.보통7그래프유니온 파인드+2아직 제출이 없습니다2초1024 MB지문만 제공
가희와 여행가요각 간선이 비용과 건설 가능 시각을 가지며, 1번 도시가 n개 도시를 모두 연결하는 최소 비용 간선 집합을 골랐을 때 연합이 완성되는 시각을 구한다.보통7최소 신장 트리유니온 파인드+2아직 제출이 없습니다1.5초512 MB지문만 제공
Urban geography연결 가중 그래프에서 최대 간선 가중치와 최소 간선 가중치의 차이가 가장 작은 신장 트리를 골라 간선 번호를 출력한다.보통7최소 신장 트리정렬+2아직 제출이 없습니다2초1024 MB지문만 제공
연결하기특정 과정으로 만들어진 가중치 연결그래프와 K개의 정점이 주어질 때, 주어진 K개의 정점을 모두 연결하는 부분그래프의 최소 간선 가중치 합을 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다5초1024 MB지문만 제공
Hexagonal Tiling변 길이가 N인 정육각형을 단위 마름모로 빈틈없이 채우되, 놓을 수 있는 각 마름모 위치마다 비용이 주어질 때 전체 비용의 최솟값을 구한다.보통7그래프최소 신장 트리아직 제출이 없습니다4초1024 MB지문만 제공
패널 최적화(Easy)각 격자의 전압을 정수만큼 바꾸며 B[i][j]의 비용을 치르고, 인접한 두 격자의 부호 조합으로 정해지는 에너지 총합이 최대가 되도록 만든다.보통7그래프최소 신장 트리+2아직 제출이 없습니다4초1024 MB지문만 제공
Random Interactive MST Bot완전 그래프의 간선 가중치를 두 개씩 비교하는 질의만으로 최소 신장 트리를 6000번 이내의 질의로 출력한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초2048 MB지문만 제공
Composius' Wrath가중치가 있는 연결 무향 그래프에서 간선 길이가 소수인 간선의 수가 최대가 되는 신장 트리를 찾아, 소수 길이 간선 수와 그렇지 않은 간선 수를 출력한다.보통7최소 신장 트리유니온 파인드+2아직 제출이 없습니다1초2048 MB지문만 제공
대도시 구축두 마을을 잇는 도로 비용이 a+b일 때, 최대 두 쌍의 건설 금지 구간이 주어진 상황에서 N개 마을을 모두 연결하는 최소 비용을 구한다.보통7그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB지문만 제공
떡국회사별 사무소가 있는 도시에만 경비를 추가로 배치할 때, 한쪽 끝에만 경비가 있는 협력 간선 수의 합을 최소로 만든다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초128 MB채점 가능
크루스칼의 공고유한 가중치를 가진 그래프에서 크루스칼 재구성 트리를 구성해 두 정점을 연결하는 최소 온도와 그 온도에서 도달 가능한 정점 수를 구하는 문제입니다.어려움8최소 신장 트리유니온 파인드+2아직 제출이 없습니다2초128 MB채점 가능
두 번째로 작은 스패닝 트리최소 스패닝 트리를 구한 뒤, 그보다 가중치가 엄밀히 더 큰 스패닝 트리 중 가장 작은 것을 찾고 없으면 -1을 출력합니다.어려움8최소 신장 트리트리+2아직 제출이 없습니다2초128 MB채점 가능
복제 로봇시작점과 최대 250개의 키가 있는 미로에서, 시작점이나 키 위치에서만 분裂 가능한 로봇들이 모든 키를 찾는 데 필요한 총 이동 거리의 최솟값을 구합니다.어려움8최단 경로최소 신장 트리+2아직 제출이 없습니다2초128 MB채점 가능
지진 복구비용과 시간이 있는 그래프에서 (F - 총비용)/총시간을 최대화하는 신장트리를 찾는 문제로, 이분탐색과 MST를 결합해야 합니다.어려움8최소 신장 트리이분 탐색+2아직 제출이 없습니다2초128 MB채점 가능
비용가중치 그래프에서 두 정점이 분리될 때까지 가장 작은 가중치 간선을 반복 제거하는 과정의 비용을 모든 정점 쌍에 대해 합산해 1e9로 나눈 나머지를 구하는 문제입니다.어려움8유니온 파인드최소 신장 트리+1아직 제출이 없습니다1초128 MB채점 가능
행성 터널3차원 좌표의 N개 행성 사이에서 두 점의 최소 축 거리를 비용으로 삼아 모든 행성을 연결하는 최소 스패닝 트리 비용을 구합니다.어려움8최소 신장 트리정렬+1아직 제출이 없습니다1초128 MB채점 가능
국내 네트워크아파트를 모두 연결하는 신장 트리를 고르고 각 간선에 두 종류의 케이블을 재고 제한 안에서 배정해 최소 비용을 구하거나 불가능함을 판정합니다.어려움8최소 신장 트리동적 계획법+1아직 제출이 없습니다2초64 MB채점 가능
티켓 투 라이드가중치 그래프와 네 쌍의 도시가 주어질 때 네 쌍을 모두 연결하는 부분그래프의 최소 총 비용을 구합니다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
'가장 짧은' 경로 쌍0번 노드에서 N-1번 노드까지 정점과 간선이 겹치지 않는 두 경로의 총 비용을 최소화하거나 불가능함을 판별합니다.어려움8그래프최단 경로+1아직 제출이 없습니다1초128 MB채점 가능
안정적인 네트워크그래프마다 어떤 간선 하나를 제거해도 연결 상태가 유지되는 최소 비용 부분 그래프를 찾고, 없으면 불가능을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
전력망 배선8x8 이하 격자에서 모든 거주 구역을 발전소에 연결하는 최소 크기 연결 집합의 개수를 10억으로 나눈 나머지를 구한다.어려움8동적 계획법그래프+2아직 제출이 없습니다1초128 MB채점 가능
패닉 룸방과 문, 침입자 위치, 패닉 룸이 주어졌을 때 침입자가 패닉 룸에 도달하지 못하도록 잠가야 하는 문의 최소 개수를 구하고, 불가능하면 PANIC ROOM BREACH를 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
국보각 유물이 비트마스크로 주어진 감시 지점들을 가지는 격자에서, 일부 유물을 고용 경비로 바꾸어 남은 모든 유물의 감시 지점에 경비가 서 있도록 하면서 고용 수를 최소화한다.어려움8그리디최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
금연 부탁드립니다인접한 방 사이 통로의 넓이가 주어진 격자에서 입구와 주방을 서로 다른 구역으로 분리하도록 방을 둘로 나누고, 잘린 통로마다 넓이당 1000유로에 1000유로를 더한 비용의 최솟값을 구한다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다3초512 MB채점 가능
첩보원첩보원들이 만나 정보를 교환하고, 보내는 첩보원들이 남은 첩보원의 정보를 모두 알도록 회의와 파견 인원을 정해 총비용을 최소화한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다5초128 MB채점 가능
섬 둘레에 울타리 치기서로 떨어진 다각형 섬들의 변 N개와 정점 간 대칭 뱃삯 행렬이 주어질 때, 아무 정점에서 시작해 모든 섬을 울타리로 둘러싸는 최소 왕복 비용을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
거미 사이먼고른 간선들의 총 길이에서 가장 긴 간선 길이의 두 배를 뺀 값이 최소가 되는 연결 부분 그래프를 찾고, 그래프가 연결되어 있지 않으면 disconnected를 출력한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다2초128 MB채점 가능
통행료새로 지은 K개의 도로에 통행료를 정해 모든 사람이 1번 도시로 가는 최소 신장 트리를 구성할 때 자신의 수익이 최대가 되도록 만든다. K는 20 이하이다.어려움8최소 신장 트리그리디+2아직 제출이 없습니다3초128 MB채점 가능
염소 밧줄n개의 점에 반지름을 배정하되 모든 쌍에서 r_i + r_j가 두 점 사이 거리 이하가 되도록 하고, 반지름 합의 최댓값을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다8초128 MB채점 가능
순회 여행모든 도시를 연결하도록 국유 도로는 팔아 이익을 얻고 민영 도로는 사서 비용을 내되, 재정에서 지출하는 순액이 최소가 되도록 도로망을 구성하는 문제다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB채점 가능
소풍 계획모든 형제가 Park에 도착하고 주차장에 최대 s대의 차만 세울 수 있을 때, 총 주행 거리의 최솟값을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
대피 계획건물별 인원과 대피소별 수용력, 그리고 하나의 유효한 배정 계획이 주어질 때, 이 계획이 모든 유효한 계획 가운데 총 이동 시간을 최소로 만드는지 판정한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
그래프 파괴하기방향 그래프의 모든 간선을 지우기 위해 각 정점에서 들어오는 간선 또는 나가는 간선을 제거하는 비용의 최솟값을 구합니다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB채점 가능
스패닝 트리같은 가중치를 가진 간선이 최대 4개인 연결 가중치 다중 그래프에서 최소 신장 트리의 개수를 1000003으로 나눈 나머지로 구한다.어려움8최소 신장 트리유니온 파인드+1아직 제출이 없습니다1초128 MB채점 가능
여행사여행에 데려갈 고객을 골라, 만족하지 못한 사회적 요구마다 패널티를 내고 남는 이익이 최대가 되도록 한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초128 MB채점 가능
부정할 수 없는 권리삼각형 산들이 이어진 능선 위의 안테나들을 시야가 통하는 구간으로 모두 연결하는 데 필요한 추가 안테나 최소 개수를 구합니다.어려움8기하그래프+2아직 제출이 없습니다1초128 MB채점 가능
압수르디스탄의 도로모든 도시 쌍 최단 거리 표를 만족하는 N개 도로 연결망 중 총 길이가 가장 작은 값을 구합니다.어려움8최소 신장 트리그래프+1아직 제출이 없습니다5초128 MB채점 가능
입자 교환주어진 각 출발 쌍에 대해 전선으로 이어진 그래프에서 두 입자를 한 번에 하나씩 이웃 노드로 옮겨 위치를 맞바꾸되 두 입자 사이 최소 거리가 최대가 되게 합니다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다5초256 MB채점 가능
떠 있는 섬위치 p와 차수 상한 d가 있는 모든 섬을 위치 차이 비용의 다리로 가장 싸게 연결하고 불가능하면 -1을 출력합니다.어려움8동적 계획법최소 신장 트리+1아직 제출이 없습니다8초512 MB채점 가능
판게아 2초기 트리에 새 도로가 추가될 때마다 모든 도시를 연결하는 최소 총 길이를 구하고 테스트 케이스마다 답들의 XOR을 출력합니다.어려움8최소 신장 트리트리아직 제출이 없습니다20초256 MB채점 가능
카드 모두 잇기두 카드 중 큰 수를 작은 수로 나눈 나머지를 비용으로 삼아 모든 카드를 연결할 때 전체 비용을 최소화합니다.어려움8최소 신장 트리정수론+1아직 제출이 없습니다5초768 MB채점 가능
다리 건설 (작은 버전)격자 위의 모든 섬을 다리로 연결하되, 각 다리의 비용이 기지와 연결된 가장 가까운 숲에서의 거리에 따라 커질 때 최소 총 비용을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다5초512 MB채점 가능
다리 건설 (라지)숲에서 출발해 모든 섬을 다리로 연결하되, 각 다리 비용이 가장 가까운 숲에서의 이동 거리일 때 최소 총 작업 시간을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다5초512 MB채점 가능