都市間貨物輸送問題のグラフアルゴリズム解法
問題1：都市間の最短経路探索
この問題では、都市間の輸送経路における最短距離を求めます。幅優先探索を応用したアルゴリズムを実装します。
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;
// グラフの辺を表す構造体
struct Connection {
int destination; ...
7月24日 03:34 投稿
重み付き木の分割処理
木構造の分割処理
基本概念
木の分割処理：木構造を複数の非交差チェーンに分割する手法で、主に重み付きチェーン分割を用いる。以下の操作をサポート：
ノードxからノードyまでの最短経路上の全ノードの値の更新
ノードxからノードyまでの最短経路上の全ノード値の合計取得
ノードxとその部分木の値の更新
ノードxとその部分木の値の合計取得
重み付き子ノード：ノ ...
7月11日 23:30 投稿
グラフ理論：K値の最大化問題 - 二分探索とシミュレーションによる解法
グラフ理論：K値の最大化問題 - 二分探索とシミュレーションによる解法
問題文
n個の頂点とm辺の単純無向グラフが与えられます。このグラフを完全グラフに補完する必要があります。補完のルールは、あらかじめパラメータKを選び、各ステップで「頂点uとvの間に辺が存在せず、かつ両頂点の次数の和がK以上」である辺のみを追加することです。このルールに従って辺を追加し ...
6月6日 17:45 投稿
01迷路の探索と到達可能セル数の計算
問題概要
n×nのサイズの迷路があり、各セルには0または1が書かれています。現在位置が0の場合、上下左右の隣接する4つのセルのうち1のセルに移動できます。同様に、現在位置が1の場合は、隣接する0のセルに移動可能です。この迷路に対して、指定された開始位置から移動可能なセルの総数（開始位置を含む）を求める問題です。
入力形式
1行目：正整数 n, m（迷路のサイズと ...
6月2日 22:01 投稿
深さ優先探索（DFS）の実装と応用
基本原理：
深さ優先探索は、開始ノードから出発し、一つの分岐を深く進み続けます。葉ノードまたは進めなくなったノードに到達するまで探索を続けます。
探索が葉ノードまたは進めなくなったノードに到達した場合、未探索の前のノードに戻り、他の分岐の探索を続けます。
既に訪問したノードをマークすることで、同じ経路での重複訪問を避けます。
DFSアルゴリズムのス ...
5月31日 11:33 投稿
コーススケジュールII - トポロジカルソート - DFS・BFSによる解法
問題概要
0からnumCourses-1までの整数で表される複数のコースが存在します。配列prerequisitesの各要素prerequisites[i] = [ai, bi]は、コースaiを受講する前にbiを完了する必要があることを示します。
すべてのコースを受講可能な順序を返してください。複数の有効な順序が存在する場合は、そのいずれかを返します。不可能な場合は空配列を返します。
例1
入力: numCou ...
5月30日 02:57 投稿