ABC352コンテスト問題解説
問題A: 停車可能区間の判定
ある区間内に指定された位置が含まれるかを判定する問題です。xとyの大小関係によって、区間の方向が変わる点に注意が必要です。
コード例
#include <iostream>
#include <algorithm>
int main() {
int n, x, y, z;
std::cin >> n >> x >> y >> z;
bool result = false;
if (x ...
7月7日 21:07 投稿
NOIP2013 提高組: 貨物輸送経路の最大最小辺問題
問題概要
無向グラフが与えられ、各辺には重みが付与されています。クエリでは2頂点間の経路における最小辺重みの最大値を求める必要があります。グラフは非連結の可能性があり、効率的な解法が求められます。
解法アプローチ
最適経路は最大ボトルネック生成木(MBST)上に存在します。MBSTはKruskal法を重み降順で適用して構築します。非連結グラフ対応のため、Union-Find ...
7月1日 17:43 投稿