Graph Template
(lib/graph/graph-template.hpp)

• View this file on GitHub
• Last update: 2021-11-09 20:40:43+09:00
• Include: #include "lib/graph/graph-template.hpp"

説明

length

• lint
• 長さ。前は edge の最後を length cost にして型をいじっていたがやり方を変えた(後述)
• Matrix 用に残してるけどイランかも

edge

• struct{ int src, to, id; }
• 辺。(src, to, id) は (始点、終点、辺番号(問題文で与えられる順番など))
• cost は、代わりに辺番号を持つ。
• 例えば問題文で辺の (src, to, 辺の長さ) が (a[i], b[i], c[i]) として与えられるなら、辺 e の長さは c[e.id] と表す
• 辺がいくつ情報を持っていても nanka[e.id] で表せるのでこの中身を触る必要はない

Graph

• vector<vector<edge>>
• 隣接リスト。なんでかわからんけど ‘G’raph と ‘e’dge がしっくりくる
• add_edge(src, to, (id), (directed)): 辺追加
  • directed: 有向なら 1 そうでなければ 0

Matrix

• vector<vector<length>>
• 隣接行列。warshall-floyd のみ?
• add_edge(src, to, (cost), (directed)): 辺追加
  • directed: 有向なら 1 そうでなければ 0

Verified with

• test/graph/bfs.test.cpp
• test/graph/dijkstra.test.cpp
• test/graph/warshall-floyd.test.cpp

Code

#pragma once
using length = lint;
struct edge{
	int src, to, id;
	edge() = default;
	edge(int src, int to, int id = 0): src(src), to(to), id(id){}
};

using Edges = vector<edge>;
class Graph: public vector<Edges>{
public:
	Graph(int n){
		this->resize(n);
	}
	void add_edge(edge e, bool directed = 0){
		(*this)[e.src].push_back(e);
		if(!directed)(*this)[e.to].push_back(edge(e.to, e.src, e.id));
	}
	void add_edge(int src, int to, int id = 0, bool directed = 0){
		(*this)[src].push_back(edge(src, to, id));
		if(!directed)(*this)[to].push_back(edge(to, src, id));
	}
};
class Matrix: public vector<vector<length>>{
public:
	Matrix(int n, length inf = 2*linf){
		this->resize(n, vector<length>(n, inf));
		for(int i = 0; i<n; ++i)(*this)[i][i] = 0;
	}
	void add_edge(edge e, length cost, bool directed = 0){
		if((*this)[e.src][e.to]>cost)(*this)[e.src][e.to] = cost;
		if(!directed)if((*this)[e.to][e.src]>cost)(*this)[e.to][e.src] = cost;
	}
	void add_edge(int src, int to, length cost, bool directed = 0){
		if((*this)[src][to]>cost)(*this)[src][to] = cost;
		if(!directed)if((*this)[to][src]>cost)(*this)[to][src] = cost;
	}
};


/*
* @title Graph Template
*/

#line 2 "lib/graph/graph-template.hpp"
using length = lint;
struct edge{
	int src, to, id;
	edge() = default;
	edge(int src, int to, int id = 0): src(src), to(to), id(id){}
};

using Edges = vector<edge>;
class Graph: public vector<Edges>{
public:
	Graph(int n){
		this->resize(n);
	}
	void add_edge(edge e, bool directed = 0){
		(*this)[e.src].push_back(e);
		if(!directed)(*this)[e.to].push_back(edge(e.to, e.src, e.id));
	}
	void add_edge(int src, int to, int id = 0, bool directed = 0){
		(*this)[src].push_back(edge(src, to, id));
		if(!directed)(*this)[to].push_back(edge(to, src, id));
	}
};
class Matrix: public vector<vector<length>>{
public:
	Matrix(int n, length inf = 2*linf){
		this->resize(n, vector<length>(n, inf));
		for(int i = 0; i<n; ++i)(*this)[i][i] = 0;
	}
	void add_edge(edge e, length cost, bool directed = 0){
		if((*this)[e.src][e.to]>cost)(*this)[e.src][e.to] = cost;
		if(!directed)if((*this)[e.to][e.src]>cost)(*this)[e.to][e.src] = cost;
	}
	void add_edge(int src, int to, length cost, bool directed = 0){
		if((*this)[src][to]>cost)(*this)[src][to] = cost;
		if(!directed)if((*this)[to][src]>cost)(*this)[to][src] = cost;
	}
};


/*
* @title Graph Template
*/

Back to top page