グラフ構造っぽいやつ

graph.h

#pragma once

#include <vector>
#include <list>

// vectorの再配置されたら死ぬ
template<class T=int, class W=int, class F=int>
class graph {
public:
	struct node;
	struct edge;

	// 頂点数ははじめに決めておく. 辺はあとで追加する.
	graph(int V = 1024*1024) : _vs(V), _es() {}

	// 頂点はg.v(1)のような感じで参照. 辺は見ちゃダメ.
	node &v(int i) { return _vs.at(i); };
	
	// dirをtrueにすると無向辺(双方向辺)に
	void add(int vi, int vj, bool dir=false, W weight=1, F flow=0, F cap=1) {
		node *f = &_vs[vi], *t = &_vs[vj];
		_es.push_back(edge{f,t,weight,flow,cap});
		edge *e = &_es.back();
		f->inc.push_back(e);
		f->adj.push_back(t);
		if(dir) {
			_es.push_back(edge{t,f,weight,flow,cap});
			edge *e2 = &_es.back();
			t->inc.push_back(e2);
			t->adj.push_back(f);
		}
	}
	
private:
	std::vector<node> _vs;
	std::list<edge> _es;
};

template<class T, class W, class F>
struct graph<T,W,F>::node {
	T data;
	std::list<edge *> inc;
	std::list<node *> adj;
};

template<class T, class W, class F>
struct graph<T,W,F>::edge {
	node *from, *to;
	W weight;
	F flow, cap;
};