7K4B blog

猫でも分かる何か

NyaaLIB::GT_GridGraph

グリッドをグラフに変換する

コンストラク

  • GT_GridGraph(ysize, xsize, exsize = 0): (ysize, xsize) のグリッドをグラフに変換(exsizeは超頂点の数)

メンバ関数

  • Vertex(y, x): グリッド座標 (y, x) に対応する頂点インデックスを返す
  • ExVertex(ll ex): 超頂点の頂点インデックスを返す(引数は0-indexで指定)
  • AddDirectedEdge(g, vnow, vnext, cost): 頂点指定で有向グラフを張る(特に超頂点を使うときに便利)
  • AddDirectedEdge(g, ynow, xnow, ynext, xnext, cost): グリッド座標指定で有向グラフを張る
  • AddUndirectedEdge(g, vnow, vnext, cost): 頂点指定で無向グラフを張る(特に超頂点を使うときに便利)
  • AddUndirectedEdge(g, ynow, xnow, ynext, xnext, cost): グリッド座標指定で無向グラフを張る
#include <bits/stdc++.h>

namespace NyaaLIB
{
	struct GT_GridGraph
	{
		using ll = long long;
		using wgraph = std::vector<std::vector<std::pair<ll, ll>>>;
		ll ysize, xsize, exsize;
		GT_GridGraph(ll ysize, ll xsize, ll exsize = 0) : ysize(ysize), xsize(xsize), exsize(exsize) {}
		ll Vertex(ll y, ll x) { return y * xsize + x; }
		ll ExVertex(ll ex) { return ysize * xsize + ex; }
		void AddDirectedEdge(wgraph& g, ll vnow, ll vnext, ll cost) { g[vnow].push_back({ vnext, cost }); }
		void AddDirectedEdge(wgraph& g, ll ynow, ll xnow, ll ynext, ll xnext, ll cost) { g[Vertex(ynow, xnow)].push_back({ Vertex(ynext, xnext), cost }); }
		void AddUndirectedEdge(wgraph& g, ll vnow, ll vnext, ll cost) { g[vnow].push_back({ vnext, cost }), g[vnext].push_back({ vnow, cost }); }
		void AddUndirectedEdge(wgraph& g, ll ynow, ll xnow, ll ynext, ll xnext, ll cost) { g[Vertex(ynow, xnow)].push_back({ Vertex(ynext, xnext), cost }), g[Vertex(ynext, xnext)].push_back({ Vertex(ynow, xnow), cost }); }
	};
}

実装例
https://atcoder.jp/contests/abc184/submissions/31830448