cho.sh

문제

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

전체 결과문제 366개
제목난이도유형정답자시간 제한메모리 제한채점
영웅은 죽지 않아요되살릴 영웅의 부분집합을 골라 양 끝이 모두 선택된 결속의 보상을 얻고, 보상 합에서 부활 비용을 뺀 값이 최대가 되게 한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
공지 전파 네트워크학년 단체 채팅은 무료로 전파되므로, 세 학년을 모두 포함하는 친구 연결 최소 비용을 만들도록 시작 학생을 골라야 한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다5초512 MB채점 가능
벤자민 고무나무연결된 가중 무방향 그래프의 정점을 공집합이 아닌 두 그룹으로 나눌 때, 두 그룹을 잇는 간선의 가중치 합이 최소가 되도록 한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다3초512 MB채점 가능
아름다운 그래프N개 정점의 완전그래프에서 각 간선의 비용이 1 또는 2일 때, 모든 그래프에 대해 차수가 2 이하인 최소 신장 트리(경로 모양)의 개수를 합해 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
간선 끊어가기가중 무방향 그래프에서 간선을 하나씩 지우다가 s와 t가 분리되는 순간 멈출 때, 그때까지 지운 간선 무게 합의 최댓값을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
악덕 나라평면 위 n개 도시와 기존 도로 m개가 주어질 때, 다른 도시를 지나지 않는 선분으로 최소 개수의 도로를 추가해 전체를 연결하면서 길이 제곱 합을 최대로 만든다.어려움8최소 신장 트리유니온 파인드+2아직 제출이 없습니다2초512 MB채점 가능
새 등산로 개척정점을 특별과 일반으로 나눈 그래프에서 특별-일반 간선을 정확히 w개 포함하는 최소 비용 신장 트리를 찾는다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다2초512 MB채점 가능
헤븐스 키친두 chef가 붙는 날의 평점을 (C_A+C_B)/|P_A-P_B|의 내림으로 정의할 때, N-1경기의 평점 합을 최대로 만드는 대진과 승패를 정하고, 문제가 정한 두 규칙으로 유일하게 결정되는 대진표를 출력한다.어려움8최소 신장 트리유니온 파인드+2아직 제출이 없습니다1초128 MB채점 가능
월요병건설 비용이 있는 칸, 벽이 있는 칸, 벽을 세울 수 없는 칸으로 이루어진 N×M 격자에서 (1,1)에서 (N,M)으로 가는 모든 경로를 막는 최소 비용을 구하고, 막을 수 없으면 -1을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB채점 가능
최소 비용 배수망현재 사용 중인 신장 트리와 추가 간선들이 주어지고 한 간선에만 할인을 적용할 수 있을 때, 최소 비용 신장 트리로 가기 위해 필요한 최소 교체 횟수를 구한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다3초512 MB채점 가능
황제의 도로각 도로를 반드시 포함하는 최소 신장 트리의 총 비용을 모든 질의에 대해 오프라인으로 구한다.어려움8최소 신장 트리유니온 파인드+1아직 제출이 없습니다1초1024 MB채점 가능
노천 채굴각 블록의 가치와 채굴 비용, 그리고 먼저 캐야 하는 선행 관계가 주어질 때, 이 관계에 닫힌 부분집합 중 이익이 최대인 것을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB채점 가능
새로운 주 나누기정점 1과 n을 서로 다른 편에 두고 그래프를 둘로 나눌 때, 잘린 간선들의 가중치를 XOR한 값이 최대가 되도록 만드는 문제이다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
그래프와 최소 스패닝 트리연결된 가중 무향 그래프의 각 간선마다 그 간선을 반드시 포함하는 최소 신장 트리의 가중치 합을 구해 출력한다.어려움8최소 신장 트리유니온 파인드+2아직 제출이 없습니다2초512 MB채점 가능
최대 전략적 절약N개 행성 각각에 M개 도시가 있고 같은 구조의 항로와 차원문이 반복되는 그래프에서, 연결성을 유지하며 제거할 수 있는 최대 유지비 합을 구한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다2초512 MB채점 가능
Rainbow Graph각 k마다 파란색과 초록색 간선만으로, 그리고 빨간색과 초록색 간선만으로 모든 노드가 연결되도록 정확히 k개의 간선을 골라 최소 가중치 합을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB지문만 제공
크루즈 퀘일간 두 개 버티는 모든 단순 이동 경로 쌍을 최소 비용의 감시 간 집합이 막도록 비용 합 최솟값을 구합니다.어려움8그래프유니온 파인드+2아직 제출이 없습니다3초512 MB채점 가능
수도를 연결하기각 수도의 차수가 정확히 1이 되도록 비수도 도시를 최소 비용 유로clidean 집합으로 연결합니다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
Directions각 표는 한 벡터 방향으로의 이동을 허용하므로, 벡터들이 평면 전체를 생성하도록 하는 최소 비용 부분집합을 고른다.어려움8기하그래프+1아직 제출이 없습니다4초512 MB지문만 제공
XOR MST두 정점 사이 간선의 가중치가 두 정점 레이블의 XOR인 완전 그래프에서 최소 신장 트리의 총 비용을 구한다.어려움8트라이최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
Compound Escape가중치가 있는 N×K 격자에서 모든 칸을 하나의 연결된 부분그래프로 묶는 최소 비용 간선 집합의 개수를 10^9+7로 나눈 나머지를 구한다.어려움8동적 계획법최소 신장 트리+2아직 제출이 없습니다2초512 MB지문만 제공
최대 이익고객 그룹이 두 중계소를 모두 사용할 때만 수익을 내도록 중계소를 지을지 정해 총수익에서 건설 비용을 뺀 최대 이익을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초256 MB채점 가능
MST and RectanglesN×N 영행렬에서 Q개의 질의가 두 직사각형 영역에 W를 더해 완전 그래프의 간선 가중치를 만든 뒤, 그 최소 신장 트리의 비용을 출력한다.어려움8동적 계획법그리디+2아직 제출이 없습니다8초1024 MB지문만 제공
다리 만들기 2작은 격자에서 섬들을 바다 위의 길이 2 이상 직선 다리로 모두 연결하되 다리 길이 합이 최소가 되게 하고, 불가능하면 -1을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB채점 가능
저항선수들이 시간에 따라 떠나고 돌아올 때, 매 변화 후 두 팀으로 나누었을 때 깨진 우정 관계의 손실을 뺀 최대 가치를 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
Planar Max Cut평면 그래프와 각 간선의 비용이 주어질 때, 두 집합으로 정점을 나누어 경계를 지나는 간선 비용의 합이 최대가 되는 분할을 구해 출력한다.어려움8그래프최단 경로+2아직 제출이 없습니다7초512 MB지문만 제공
Milliarium Aureum주요 도로가 트리를 이루고 일반 도로가 섞인 그래프에서, 각 도시로 가는 모든 경로의 최소 도로 폭을 주요 도로가 최대화하는 로마 후보 도시를 모두 찾는다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB지문만 제공
Always Online임의의 두 정점 사이에 서로소인 경로가 많아야 두 개인 연결 그래프에서, 모든 정점 쌍에 대해 s XOR t XOR flow(s,t)의 합을 구한다. 여기서 flow는 두 정점 사이 경로의 최소 간선 가중치 중 최댓값이다.어려움8그래프트리+2아직 제출이 없습니다4초512 MB지문만 제공
Milk Candy각 NPC에서 정확히 ki개의 힌트를 사서 n개의 미지수를 모두 알아낼 수 있도록 하는 최소 비용을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB지문만 제공
Honeycomb일부 변만 지나갈 수 있는 n행 m열 벌집에서 모든 특수 칸 쌍 사이를 끊는 데 필요한 최소 변 수의 합을 구한다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다6초512 MB지문만 제공
Lumbo Jumbo간선 비용을 한 번만 내면 되는 3 x N 격자에서 P개의 중요한 칸을 모두 방문하는 최소 비용 경로를 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB지문만 제공
Constellation 3별을 검게 칠하는 최소 비용을 구한다. 어떤 건물이 없는 직사각형도 두 개 이상의 별을 담지 않아야 한다.어려움8동적 계획법그래프+2아직 제출이 없습니다1초512 MB지문만 제공
Kingdom Connectivity평면 직선 그래프에서 각 벽의 비용이 주어질 때, 모든 벽의 양쪽이 외부에서 접근 가능하도록 문을 설치할 벽의 최소 비용 집합을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB지문만 제공
Communication Between Robots로봇들이 일정한 속도로 직선 운동하며 한 시점에 연결된 통신망을 이룰 때, 그 시점의 최소 신장 트리 거리 합의 최솟값을 구한다.어려움8최소 신장 트리기하+1아직 제출이 없습니다7초512 MB지문만 제공
팀 가르기N명의 임직원을 공격팀과 방어팀으로 나누어 공격력 합과 방어력 합에서 태스크 포스 내에서 팀이 갈린 쌍마다 부과되는 감점을 뺀 값이 최대가 되도록 배정을 정한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초256 MB지문만 제공
Logistical Metropolis연결된 가중 그래프의 각 정점에 대해 그 정점이 최대 차수를 갖도록 강제할 때의 최소 신장 트리 비용을 구한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다3초1024 MB지문만 제공
소가 길을 건너간 이유 2020위 N개, 아래 M개 점을 잇는 교차 없는 N+M-1개 선분으로 만든 항로에서 모든 헛간 쌍의 최단 거리 제곱 합을 최소화한다.어려움8최소 신장 트리기하+1아직 제출이 없습니다1초1024 MB지문만 제공
Mountains and Valleys가중치 1인 간선이 신장 트리를 이루고 나머지 간선은 ceil(N/3) 이상인 그래프에서 모든 지점을 방문하는 최소 비용 경로를 구한다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다7초512 MB지문만 제공
자매 도시가중치가 있는 연결 그래프에서, 주어진 두 도시 사이를 충돌 없이 오가는 두 경로의 병목(지나는 도로 가중치의 최댓값)을 최소로 만드는 값을 각 질의마다 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB지문만 제공
Rigged Roads연결 그래프와 신장 트리 R이 주어질 때, R이 유일한 최소 신장 트리가 되도록 1부터 E까지의 가중치를 배정하되 그 수열이 사전순으로 가장 작게 만든다.어려움8그래프유니온 파인드+2아직 제출이 없습니다2초512 MB지문만 제공
Simurgh연결 그래프에서 숨겨진 왕실 신장 트리에 속한 간선을 찾는다. 임의의 신장 트리에 포함된 왕실 간선 수를 세는 질의를 q번 이하로 사용한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다3초512 MB지문만 제공
Parity Constraint Minimum Spanning Tree스패닝 트리의 비용 합이 홀수인 최솟값과 짝수인 최솟값을 구하고, 해당하는 트리가 없으면 -1을 출력한다.어려움8최소 신장 트리유니온 파인드+1아직 제출이 없습니다1초1024 MB지문만 제공
아침은 고구마야 (Normal)루트가 있는 선인장 형태의 그래프에서 끊기는 간선 강도의 합이 최소가 되도록 자를 때, 온전히 남는 단순 사이클 질량의 합을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다3초512 MB지문만 제공
아침은 고구마야 (Hard)뿌리부터 이어지는 덩이뿌리를 최대 질량으로 뽑기 위해 자르는 간선 강도 합을 최소화할 때, 수확하는 고구마 질량의 합을 구한다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다3초512 MB지문만 제공
Premier Leaguen마리의 포켓몬을 앤디와 조던 중 한 명에게 배정하고, 구매 비용에서 낙찰가를 뺀 값과 두 포켓몬이 서로 다른 사람에게 배정된 경기의 비용을 더해 최소 총비용을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB지문만 제공
Subway Map일부 길이가 알려지고 일부는 미지인 연결 그래프에서, 모든 역을 1번 역과 잇는 케이블 간선 집합이 최소 신장 트리가 되도록 각 미지 터널 길이의 최솟값을 구한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다4초1024 MB지문만 제공
Degree Bounded Minimum Spanning Tree모든 정점의 차수가 주어진 한도를 넘지 않으면서 간선 비용 합이 최소인 스패닝 트리를 찾고, 없으면 존재하지 않는다고 출력한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다3초1024 MB지문만 제공
Cartesian MST연결된 두 가중 그래프가 주어질 때, 두 그래프의 카테시안 곱의 최소 신장 트리 총 가중치를 구한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다1초512 MB지문만 제공
Certain Scientific Railgun모든 로봇이 지나간 점과 같은 행이나 열에 놓이도록 원점에서 출발하는 최단 격자 경로의 길이를 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB지문만 제공
아즈텍의 섬아즈텍 다이아몬드의 격자 변들 중에서 모든 밭이 경계와 연결되고 x+y가 홀수인 점은 차수가 2 이상이 되도록 최소 비용으로 고른다.어려움8최소 신장 트리그래프+1아직 제출이 없습니다5초1536 MB지문만 제공
Portals각 정점은 포털 네 개를 두 쌍의 스위치로 묶으며, 정점을 고치는 데 c_v를 지불하고 4N개 포털 위치가 모두 연결되도록 최소 비용을 구한다.어려움8그래프유니온 파인드+2아직 제출이 없습니다1초512 MB지문만 제공
Repairing관 여러 개와 그 위의 밸브, 수원, 수리 지점이 주어질 때, 밸브 일부를 잠가 수리 지점으로 가는 물을 끊으면서 닫아야 하는 관 길이의 최솟값을 구한다.어려움8기하그래프+2아직 제출이 없습니다5초512 MB지문만 제공
街を駆ける道A 진영 도시들만 이어 A와 B를, C 진영 도시들만 이어 C와 D를 연결하되 서로 교차하지 않게 도로를 지을 때 총 길이의 최솟값을 구합니다.어려움8최소 신장 트리기하아직 제출이 없습니다8초512 MB지문만 제공
Top of the Hill원기둥 모양 원반 N개가 쌓여 있을 때, 원반 가장자리 어디서든 떨어져 내릴 수 있지만 올라갈 때는 동서남북 네 지점의 엘리베이터만 쓸 수 있는 자동차의 최단 경로를 구한다.어려움8기하그래프+2아직 제출이 없습니다8초512 MB지문만 제공
Adhoc Translation웹 텍스트와 사전이 주어질 때, 서로 다른 텍스트 단어에 서로 다른 사전 단어를 배정하여 전체 편집 거리의 합을 최소화한다.어려움8동적 계획법문자열+2아직 제출이 없습니다8초512 MB지문만 제공
사이클방향 가중 그래프의 모든 정점을 정점이 겹치지 않는 단순 사이클들로 나누어 총 가중치가 최소가 되게 하거나, 불가능하면 0을 출력한다.어려움8그래프동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
조별과제 멈춰!각 질의 X, Y마다 X와 Y를 팀장으로 하는 두 개의 비어 있지 않은 조로 나누고, 연락 비용 합의 최솟값을 구한다.어려움8최소 신장 트리유니온 파인드+2아직 제출이 없습니다2초512 MB지문만 제공
Find the MST for GridH×W 격자에서 세로 간선과 가로 간선의 가중치가 네 개의 정렬된 수열로 주어질 때, 최소 신장 트리의 총 가중치를 구한다.어려움8최소 신장 트리그리디+2아직 제출이 없습니다2초512 MB지문만 제공
MIPT: Connecting People모든 주민이 연결되도록 n-1개의 수평 복도를 지어 전체 주민 쌍의 이동 시간 합을 최소화한다.어려움8동적 계획법그래프+1아직 제출이 없습니다2초512 MB지문만 제공
Evaluation각 간선의 계수를 최대로 얼마까지 올려도 그 간선이 어떤 최소 신장 트리에 포함될 수 있는지 구해 10^9로 자른 값을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다8초256 MB지문만 제공
Hristenko Olegn x m 격자가 주어지고, 같은 행이나 같은 열에 있는 두 칸을 값의 차이를 비용으로 하는 간선으로 연결한 그래프에서 최소 신장 트리의 비용을 구한다.어려움8최소 신장 트리정렬+1아직 제출이 없습니다2초512 MB지문만 제공
Specializing Villages마을을 두 집단으로 나눠 서로 다른 집단까지의 최단 거리 평균을 최소로 만들고, 그런 분할의 개수를 센다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다20초1024 MB지문만 제공
ジョイッター (Joitter)각 사용자의 공개 범위를 만족하면서 모든 사용자가 서로의 일기를 읽을 수 있도록 하는 최소 친구 등록 횟수와 그때의 최소 비용을 구한다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다1초1024 MB지문만 제공
本選会場 (Finals)N개 도시와 M개 도로로 이루어진 연결 가중 그래프에서 K개 도시를 본선 회장으로 정할 때, 한 번에 여러 선수가 같은 통행료를 나눠 낼 수 있다는 점을 이용해 모든 선수를 모으는 통행료 합의 최솟값을 구한다.어려움8그래프그리디+2아직 제출이 없습니다1초1024 MB지문만 제공
Bombs거대한 격자 위의 상자와 바위가 주어질 때, 빈 칸에 놓는 가로 또는 세로 폭탄으로 모든 상자를 부수는 최소 개수와 그 위치를 구한다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다2초1024 MB지문만 제공
전력공급건물의 부분집합을 골라 내부 잉여 전력 합에서 집합 밖으로 보내는 전력 합을 뺀 값을 최대화한다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다1초512 MB지문만 제공
토지 구입N×M 격자를 두 사람에게 나누어 각 칸의 이익과 같은 특징을 가진 인접 칸의 추가 이익 합을 최대로 만들고 그 배정을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
Reconstruction Project각 목표 너비 X마다 너비 X인 간선만으로 N개 역을 모두 연결하도록 간선 너비를 1씩 바꾸는 최소 비용을 구한다.어려움8최소 신장 트리그리디+2아직 제출이 없습니다5초1024 MB지문만 제공
Kingdom Partition마을을 세 구역으로 나누어 a는 A에, b는 B에 두고 Adrian과 Beatrice가 부담하는 도로 보수 비용의 합을 최소로 만든다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다3초512 MB지문만 제공
Village Transportation예산과 도로 건설 비용이 주어지고 각 도로의 로열티가 남은 돈에 비례할 때, 마지막에 남길 수 있는 최대 금액을 구한다.어려움8그래프이분 탐색+2아직 제출이 없습니다3초1024 MB지문만 제공
건너 아는 사이두 번호가 서로소이면 큰 값, 아니면 최대공약수를 간선 비용으로 할 때, N명이 모두 건너 아는 사이가 되도록 하는 최소 비용 합을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다0.5초1024 MB지문만 제공
You Shall Passn명의 학생을 두 학급으로 나누어, 같은 학급 학생끼리 주어지는 가산 확률을 반영했을 때 통과 학생 수의 기댓값이 최대가 되도록 배정한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
곰곰이의 식단 관리 2격자에서 (1,1)에서 (N,M)으로 가는 경로가 없어지도록 막아야 하는 빈 칸의 최소 개수를 구한다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다3.5초1024 MB지문만 제공
Pristojba각 정점의 요금 p[i]와, 정점 x에서 구간 [a,b]의 모든 정점으로 간선을 허용하는 m개의 허가가 주어질 때, 간선 비용을 p[a]+p[b]로 두고 모든 정점을 연결하는 최소 비용을 구한다.어려움8최소 신장 트리세그먼트 트리+2아직 제출이 없습니다5초1024 MB지문만 제공
함수와 최소 스패닝 트리모든 간선 가중치가 같은 이차항 계수를 갖는 이차함수일 때, 최소 스패닝 트리 가중치를 시간에 대해 적분한 값을 10^9+7로 나눈 나머지를 구한다.어려움8최소 신장 트리기하+2아직 제출이 없습니다3초1024 MB지문만 제공
Ciężarówki II가중치가 있는 연결 그래프에서 K대의 트럭을 서로 다른 출발지에서 목적지까지 옮길 때, 각 트럭 경로의 최대 간선 비용 합을 최소화한다.어려움8최소 신장 트리그리디+2아직 제출이 없습니다4초1024 MB지문만 제공
Bicycle Tour가중치가 있는 연결 그래프의 각 정점마다 그 정점에서 시작하고 끝나는 닫힌 보행 중 사용한 간선 가중치의 최댓값을 최소로 하는 값을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
Pixels각 픽셀을 검정 또는 흰색으로 칠해 보상의 합에서 인접한 픽셀의 색이 다를 때 드는 비용을 뺀 값을 최대로 만든다.어려움8그래프최소 신장 트리+1아직 제출이 없습니다2초1024 MB지문만 제공
기지 간소화가중치 트리에서 번호가 연속인 정점 구간마다 그 정점들을 연결하는 데 필요한 간선 길이 합의 최솟값을 구한다.어려움8트리최소 신장 트리+2아직 제출이 없습니다4초1024 MB지문만 제공
산지니의 여행계획직통 도로를 최소한으로 선택해 길이 합이 최대가 되게 한 뒤, 정해진 시작 도시에서 모든 도시를 방문하는 최단 경로의 길이를 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB지문만 제공
개미억장와르르맨션가중 무방향 그래프에서 모든 개미굴을 점검할 수 있도록 하되 사용된 길의 총 개수가 최소가 되는 최소 위험도합 구조를 찾고, 불가능하면 -1을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
Broken Minimum Spanning Tree주어진 신장 트리를 최소 신장 트리로 만들기 위해 트리 간선을 하나 빼고 비트리 간선을 하나 넣는 교환을 최소 몇 번 해야 하는지 구하고, 그 교환들을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초2048 MB지문만 제공
차량 모듈 제작N개의 원이 주어질 때, 접하거나 겹치면 기어가 서로 회전하고 벨트로도 연결할 수 있다. 모든 기어가 회전하도록 하는 최소 벨트 길이의 합을 구한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다2초1024 MB지문만 제공
Minimum Cost Roads원래 그래프에서 두 지점 사이의 거리가 줄어들지 않도록 도로 부분집합을 골라 유지비 합을 최소화한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
Vjeverice가중치가 있는 연결 그래프에서 최소 신장 트리 비용을 구하고, 각 간선 하나의 가중치가 바뀌는 질의마다 새로운 최소 신장 트리 비용을 출력한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다2초1024 MB지문만 제공
Internet Monopoly연결 상태에서 간선이 온라인으로 추가될 때, 모든 최소 신장 트리가 정확히 K개의 저렴한 간선을 쓰도록 가격을 정할 수 있는지 판정한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
Ralli süvakosmoses간선 k의 연료 비용이 2^k인 무방향 연결 그래프에서 두 정점 사이의 최소 연료 비용을 1e9+7로 나눈 나머지를 여러 질의에 대해 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
Water Contamination침수된 연결로 오염원이 확산될 때, 오염된 장소에서 중요한 장소로 가는 경로를 모두 끊는 최소 간선 수를 구한다.어려움8그래프최소 신장 트리아직 제출이 없습니다1초1024 MB지문만 제공
Building RoadsN개의 점이 주어질 때 최소 신장 트리를 만들고, 두 점 사이 최단 거리 중 가장 긴 값인 지름을 최소화하여 출력한다.어려움8최소 신장 트리그래프+1아직 제출이 없습니다2초1024 MB지문만 제공
스패닝 최소 트리정점 N개, 간선 M개이며 가중치가 1부터 M까지 하나씩인 단순 그래프를 만들어 최소 스패닝 트리 가중치 합이 정확히 S가 되도록 하거나, 불가능하면 -1을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
НОД объединяетn명의 학생 사이 간선 가중치를 gcd(a_u, a_v)로 두고, 간선 수가 최소인 신장 트리 중 총 가중치가 최대인 것을 구한다.어려움8정수론유니온 파인드+2아직 제출이 없습니다4초1024 MB지문만 제공
TSM각 간선 i에 l_i 이상 r_i 이하의 정수 가중치를 부여해 어떤 최소 스패닝 트리의 비용이 정확히 K가 되도록 만들 수 있는지 판정하고, 가능하면 가중치를 출력한다.어려움8최소 신장 트리유니온 파인드+2아직 제출이 없습니다8초1024 MB지문만 제공
Communications Satellite서로 겹치지 않는 원판들을 내부를 가로지르지 않고 교차하지 않는 빔으로 연결할 때 빔 길이 합의 최솟값을 구한다. 답은 접선 거리 그래프의 최소 신장 트리다.어려움8최소 신장 트리기하+2아직 제출이 없습니다3초1024 MB지문만 제공
Very Important Edge가중치가 있는 단순 연결 그래프에서 간선 하나를 지웠을 때 최소 신장 트리 무게가 가장 커지도록 하는 간선을 골라, 그 무게를 출력한다.어려움8최소 신장 트리그래프+2아직 제출이 없습니다3초2048 MB지문만 제공
Steiner tree in random graph무작위 가중 그래프에서 처음 n-k개 정점을 모두 포함하는 최소 가중 연결 부분 그래프를 찾아 간선을 출력한다.어려움8그리디그래프+2아직 제출이 없습니다2초1024 MB지문만 제공
신촌 도로망 관리와 쿼리다섯 학교의 도로 관리비가 바뀔 때마다 관리된 도로만으로 모든 정점을 연결하는 최소 비용을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2.5초1024 MB지문만 제공
Link-Cut Tree간선 i의 길이가 2^i인 무향 그래프에서 길이가 가장 짧은 단순 사이클의 간선 번호를 출력하고, 사이클이 없으면 -1을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
무빙워크각 무빙워크의 전원을 켜거나 꺼서 1번 건물에서 모든 건물로 도달 가능하게 유지하면서 최단 거리 합의 최솟값과 전원 상태를 구한다.어려움8그래프최단 경로+2아직 제출이 없습니다2초1024 MB지문만 제공
AMST간선 가중치가 t의 일차함수인 연결 그래프에서 최소 스패닝 트리 가중치가 주어진 S가 되는 t를 찾는다.어려움8최소 신장 트리기하+1아직 제출이 없습니다5초1024 MB지문만 제공
익웜 바이러스각 PC마다 다른 감염 비용이 주어질 때, 최대 K개의 PC를 직접 감염시켜 가중 간선을 따라 바이러스가 퍼지며 모든 PC를 감염시키는 최소 총비용을 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1.5초1024 MB지문만 제공