图论 wu-kan

这里用类似邻接表的方法存图。有的算法可能需要邻接矩阵,详见线性代数部分。

struct Graph
{
	struct Vertex
	{
		vector<int> o, i;		//相关出边和入边编号
		int siz, dep, top, dfn; //树链剖分中使用,依次代表子树节点数、深度、所在链的顶端节点、dfs序
	};
	struct Edge : pair<int, int>
	{
		ll len, cap; //边长、容量,图论算法使用
	};
	vector<Vertex> v; //点集
	vector<Edge> e;   //边集
	Graph(int n) : v(n) {}
	void add(const Edge &ed)
	{
		if (ed.first == ed.second)
			return; //如果有需要请拆点
		v[ed.first].o.push_back(e.size());
		v[ed.second].i.push_back(e.size());
		e.push_back(ed);
	}
	int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个孩子节点
	int fa(int u, int i = 0) { return e[v[u].i[i]].first; } //u的第i个父节点
};

最短路

Dijkstra 算法

使用示例,适用于边权为正的情况(无论有向图还是无向图),用于求单源最短路。

直接给出其优先队列优化的版本。另外,由于priority_queue并不提供修改优先级的操作,为避免重复扩展,这里选择将新元素直接插入队列并在运行时判断该点是否被处理,并不影响结果的正确性。

struct Dijkstra : Graph
{
	vector<ll> d;
	vector<int> p;
	Dijkstra(int n) : Graph(n) {}
	void ask(int s)
	{
		d.assign(v.size(), INF);
		p.assign(v.size(), e.size());
		priority_queue<pair<ll, int>> q;
		for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
		{
			ll dis = -q.top().first;
			int u = q.top().second;
			if (q.pop(), d[u] < dis)
				continue;
			for (int i = 0, k, to; i != v[u].o.size(); ++i)
				if (k = v[u].o[i], to = e[k].second,
					d[to] > d[u] + e[k].len)
				{
					d[to] = d[u] + e[k].len, p[to] = k;
					q.push(make_pair(-d[to], to));
				}
		}
	}
};

BellmanFord 算法

使用示例,直接给出其队列优化、国内称之为 SPFA 算法的版本。较之 Dijkstra 算法,此算法不够快速稳定但是可以允许负边存在,当 s 到达负权回路时会直接返回 0。稀疏图上性能优秀。

struct BellmanFord : Graph
{
	vector<ll> d;
	vector<int> p;
	BellmanFord(int n) : Graph(n) {}
	bool ask(int s)
	{
		d.assign(v.size(), INF);
		p.assign(v.size(), e.size());
		vector<int> cnt(v.size(), 0), flag(v.size(), d[s] = 0);
		for (deque<int> q(cnt[s] = flag[s] = 1, s); !q.empty(); q.pop_front())
			for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
				if (k = v[u].o[i], to = e[k].second,
					d[to] > d[u] + e[k].len)
				{
					d[to] = d[u] + e[k].len, p[to] = k;
					if (!flag[to])
					{
						if (v.size() == ++cnt[to])
							return 0;
						flag[to] = 1, q.push_back(to);
					}
				}
		return 1;
	}
};

差分约束系统

按如下方式建图、跑 SPFA:

对每个不等式$x_i−x_j\leq d$,从$j$向$i$连一条边,边长为$d$。

若不等号的方向相反,即$x_i−x_j\geq d$,则在不等式两边同时乘以$-1$,变成$x_j−x_i\leq -d$,即从$i$到$j$连一条边,边长为$d$。

Floyed 求多源最短路

不连通的权置 INF。

void floyed(Mat &a, int n) // 其实一般手打即可,没必要套这个鬼模板…
{
	for (int k = 0; k < n; ++k)
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				if (a[i][j] > a[i][k] + a[k][j])
					a[i][j] = a[i][k] + a[k][j];
}

Astar 求 k 短路

使用示例,在这个比较坑的例子中需要在调用前补一句if(s==t)++k;k 下标从 0 开始,即最短路==第 0 短路

朴素的想法是使用priority_queue从原点出发向外探索,当取出终点 t 第 k 次时就得到第 k 短路,类似 bfs 的思想,缺陷是越往后状态数越多。

我们在反向图上从$t\to s$跑 Astar 算法,通过优先展开到 s 近的状态,使搜索方向靠近答案,而不是一层一层全都展开,估价函数$f\approx g+h$,f 是估计的 s 到 t 的距离,g 是到达当前点已经点的花费,h 是预计剩下的花费。这里 h 取当前点的距离到 s 距离,可通过从 s 跑一遍 Dijkstra 可以预处理得出。

Astar 算法是只有到达终点的时候才能统计答案,这导致可能拓展很多个状态才能得到一个用来更新答案的有效状态。例如一个 n 元环,当我们到达终点之后,可能还要拓展 n 次才能得到下一个状态,于是时间复杂度就被卡到$O(nk)$。

struct Astar : Dijkstra
{
	vector<ll> ans;
	Astar(int n) : Dijkstra(n) {}
	void ask(int s, int t, int k)
	{
		Dijkstra::ask(s);
		ans.assign(k, INF);
		if (d[t] == INF)
			return;
		vector<int> cnt(v.size(), 0);
		priority_queue<pair<ll, int>> q;
		for (q.push(make_pair(-d[t], t)); cnt[s] < k && !q.empty();)
		{
			ll dis = -q.top().first;
			int u = q.top().second;
			if (u == s)
				ans[cnt[s]] = dis;
			if (q.pop(), ++cnt[u] > k)
				continue;
			for (int i = 0, k; i < v[u].i.size(); ++i)
				k = v[u].i[i], q.push(make_pair(d[u] - d[e[k].first] - e[k].len - dis, e[k].first));
		}
	}
};

网络流

ISAP 求最大流

使用示例

struct ISAP : Graph
{
	ll flow;
	vector<ll> f;
	vector<int> h, cur, gap;
	ISAP(int n) : Graph(n) {}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.first, ed.second), ed.cap = 0;
		Graph::add(ed);
	}
	ll dfs(int s, int u, int t, ll r)
	{
		if (r == 0 || u == t)
			return r;
		ll _f, _r = 0;
		for (int &i = cur[u], k; i < v[u].o.size(); ++i)
			if (k = v[u].o[i], h[u] == h[e[k].second] + 1)
			{
				_f = dfs(s, e[k].second, t, min(r - _r, e[k].cap - f[k]));
				f[k] += _f, f[k ^ 1] -= _f, _r += _f;
				if (_r == r || h[s] >= v.size())
					return _r;
			}
		if (!--gap[h[u]])
			h[s] = v.size();
		return ++gap[++h[u]], cur[u] = 0, _r;
	}
	void ask(int s, int t)
	{
		h.assign(v.size(), 0);
		cur.assign(v.size(), 0);
		gap.assign(v.size() + 2, 0);
		/*
		for (deque<int> q(h[t] = gap[t] = 1, t); !q.empty(); q.pop_front()) //优化,加了能快一点
			for (int i = 0, u = q.front(), k, to; i < v[u].o.size(); ++i)
				if (to = e[v[u].o[i]].second, !h[to])
					++gap[h[to] = h[u] + 1], q.push_back(to);
		*/
		for (f.assign(e.size(), flow = 0); h[s] < v.size();)
			flow += dfs(s, s, t, INF);
	}
};

PrimalDual 求费用流

使用示例,定义一条边的费用为流量*边长,求总费用最小的最大流。性能优秀,只能跑非负权图。

struct PrimalDual : Graph
{
	ll flow, cost;
	vector<ll> f;
	PrimalDual(int n) : Graph(n) {}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.first, ed.second), ed.cap = 0, ed.len *= -1;
		Graph::add(ed);
	}
	void ask(int s, int t) //询问s到t的最小费用最大流,答案存在flow、cost中
	{
		vector<int> p(v.size(), e.size());
		vector<ll> d(v.size(), INF), h(v.size(), 0);
		for (f.assign(e.size(), flow = cost = 0);;)
		{
			priority_queue<pair<ll, int>> q;
			for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
			{
				ll dis = -q.top().first;
				int u = q.top().second;
				if (q.pop(), d[u] < dis)
					continue;
				for (int i = 0, k, to; i < v[u].o.size(); ++i)
					if (k = v[u].o[i], to = e[k].second,
						e[k].cap > f[k] && d[to] > d[u] + e[k].len + h[u] - h[to])
					{
						d[to] = d[u] + e[k].len + h[u] - h[to], p[to] = k;
						q.push(make_pair(-d[to], to));
					}
			}
			if (d[t] == INF)
				return;
			for (int i = 0; i < d.size(); ++i)
				if (d[i] != INF)
					h[i] += d[i], d[i] = INF;
			ll _f = INF;
			for (int u = t; u != s; u = e[p[u]].first)
				_f = min(_f, e[p[u]].cap - f[p[u]]);
			for (int u = t; u != s; u = e[p[u]].first)
				cost += _f * e[p[u]].len, f[p[u]] += _f, f[p[u] ^ 1] -= _f;
			flow += _f;
		}
	}
};

EK 求费用流

使用示例,定义一条边的费用为流量*边长,求总费用最小的最大流。BellmanFord 算法找增广路,可能被卡但是可以跑负费用流(最大费用流)。

struct EdmondKarp : Graph
{
	ll flow, cost;
	vector<ll> f;
	EdmondKarp(int n) : Graph(n) {}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.first, ed.second), ed.cap = 0, ed.len *= -1;
		Graph::add(ed);
	}
	void ask(int s, int t)
	{
		vector<int> p(v.size(), e.size());
		for (f.assign(e.size(), flow = cost = 0);;)
		{
			vector<ll> d(v.size(), INF);
			vector<int> flag(v.size(), d[s] = 0);
			for (deque<int> q(flag[s] = 1, s); !q.empty(); q.pop_front())
				for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
					if (k = v[u].o[i], to = e[k].second,
						e[k].cap > f[k] && d[to] > d[u] + e[k].len)
					{
						d[to] = d[u] + e[k].len, p[to] = k;
						if (!flag[to])
							q.push_back(to), flag[to] = 1;
					}
			if (d[t] == INF)
				return;
			ll _f = INF;
			for (int u = t; u != s; u = e[p[u]].first)
				_f = min(_f, e[p[u]].cap - f[p[u]]);
			for (int u = t; u != s; u = e[p[u]].first)
				cost += _f * e[p[u]].len, f[p[u]] += _f, f[p[u] ^ 1] -= _f;
			flow += _f;
		}
	}
};

ZKW 求费用流

使用示例,定义一条边的费用为流量*边长,求总费用最小的最大流。

对于最终流量较大,而费用取值范围不大的图,或者是增广路径比较短的图(如二分图),zkw 算法都会比较快,原因是充分发挥优势。比如流多说明可以同一费用反复增广,费用窄说明不用改太多距离标号就会有新增广路,增广路径短可以显著改善最坏情况,因为即使每次就只增加一条边也可以很快凑成最短路。如果恰恰相反,流量不大,费用不小,增广路还较长,就不适合 zkw 算法了。

struct ZKW : Graph
{
	ll flow, cost;
	vector<ll> h, f;
	vector<int> vis;
	ZKW(int n) : Graph(n) {}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.first, ed.second), ed.cap = 0, ed.len *= -1;
		Graph::add(ed);
	}
	ll dfs(int u, int t, ll r)
	{
		if (r == 0 || u == t)
			return r;
		if (vis[u])
			return 0;
		ll _f = vis[u] = 1, _r = 0;
		for (int i = 0, k; r > _r && i < v[u].o.size(); ++i)
			if (k = v[u].o[i], h[e[k].second] + e[k].len == h[u])
				_f = dfs(e[k].second, t, min(r - _r, e[k].cap - f[k])), f[k] += _f, f[k ^ 1] -= _f, _r += _f;
		return _r;
	}
	void ask(int s, int t)
	{
		h.assign(v.size(), 0);
		vis.assign(v.size(), 0);
		for (f.assign(e.size(), flow = cost = 0);;)
		{
			ll _f = dfs(s, t, INF), d = INF;
			flow += _f, cost += _f * h[s];
			for (int u = 0; u < v.size(); ++u)
				for (int i = 0, k; vis[u] && i < v[u].o.size(); ++i)
					if (k = v[u].o[i], !vis[e[k].second] && e[k].cap > f[k])
						d = min(d, e[k].len + h[e[k].second] - h[e[k].first]);
			if (d == INF)
				return;
			for (int i = 0; i < v.size(); ++i)
				if (vis[i])
					h[i] += d, vis[i] = 0;
		}
	}
};

上下界有源汇网络流

T 向 S 连容量正无穷的边,将有源汇转化为无源汇。每条边容量减去下界,设$in[i]$表示流入 i 的下界之和减去流出 i 的下界之和。新建超级源汇 SS,TT,对于$in[i]>0$的点,SS 向 i 连容量为$in[i]$的边。对于$in[i]<0$的点,i 向 TT 连容量为$−in[i]$的边。

求出以 SS,TT 为源汇的最大流,如果等于$\sum ini$则存在可行流。再求出以 S,T 为源汇的最大流即为最大流。

费用流:建完图后等价于求以 SS,TT 为源汇的的费用流。

上下界费用流:先把下界的费用加入答案。

判断边是否属于某一割集

在残余网络 (还有流量的边) 中求强连通分量,顶点不在同一 SCC 且满流的边。

判断边是否为全部最小割集的边: 在上一条的基础上,还要满足起点与 S 在同一 SCC,且终点与 T 在同一 SCC。

线性规划转费用流

首先添加松弛变量,将不等号都变为等号。分别用下一个式子减去上一个式子,如果每个变量只出现了两次且符号一正一负,那么可以转化为费用流。对于每个式子建立一个点,那么每个变量对应一条边,从一个点流出,向另一个点流入。这样,对于等式右边的常数,如果是正的,对应从源点向该点连一条流量 C,费用 0 的边;如果是负的对应从该点向汇点连一条流量 −C,费用 0 的边。对于每个变量,从它系数为正的式子向系数为负的式子连一条容量为 inf,费用为它在目标函数里系数的边。这样网络流模型就构造完毕了。

欧拉路

使用示例,给定无孤立结点图 G,若存在一条路,经过图中每边一次且仅一次,该条路称为欧拉路。

  • 无向图:当仅当该图所有顶点的度数为偶数(此时为回路),或除两个度数为奇数外(作为路径的起点和终点)、其余全为偶数。
  • 有向图:当仅当该图所有顶点出度=入度(此时为回路),或一个顶点出度=入度+1(作为起点)、另一个顶点入度=出度+1(作为终点)、其他顶点出度=入度。
struct Fleury : Graph
{
	vector<int> vis, cur, p;
	Fleury(int n) : Graph(n) {}
	void dfs(int u)
	{
		for (int &i = cur[u], k; i < v[u].i.size(); ++i) //遍历原图的反向图,这里加了一个「当前弧」优化
			if (k = v[u].i[i], !vis[k] && !vis[k ^ 1])   //无向图需要同时检查反向边未被访问过
			{
				vis[k] = 1;
				dfs(e[k].first);
				p.push_back(k);
			}
	}
	void ask() //查询欧拉回路,路径上边的序号按顺序存在p中
	{
		vis.assign(e.size(), 0), cur.assign(v.size(), 0), p.clear();
		for (int i = 0; i < v.size(); ++i)
			if (v[i].i.size() % 2)
				return dfs(i);
		dfs(0);
	}
};

混合图欧拉回路判定

首先给无向边随便定一个方向,设$\deg x$为 x 连出去的边数 − 连入 x 的边数。若存在$\deg x$为奇数,或者图不连通,则无解。否则建立源点 S,汇点 T。对于一个点 x,若$\deg x>0$,则 S 向 x 连边,容量$\frac{\deg x}{2}$;若$\deg x<0$,则 x 向 T 连边,容量$-\frac{\deg x}{2}$。 对于一条定了向的无向边$x\to y$,x 向 y 连边,容量 1,求出最大流,若与 S 和 T 连的每条边都满流,则有解。

连通性

无向图求割和双连通分量

使用示例 1

使用示例 2

  • 割边:在连通图中,删除了连通图的某条边后,图不再连通。这样的边被称为割边,也叫做桥。
  • 割点:在连通图中,删除了连通图的某个点以及与这个点相连的边后,图不再连通。这样的点被称为割点。构造 dfs 搜索树,在树上有两类节点可以成为割点:
    • 对根节点 u,若其有两棵或两棵以上的子树,则该根结点 u 为割点;
    • 对非根非叶节点 u,若其中的某棵子树的节点均没有指向 u 的祖先节点的回边,说明删除 u 之后,根结点与该棵子树的节点不再连通;则节点 u 为割点。

对于一个无向图的子图,当删除其中任意一条边后,不改变图内点的连通性,这样的子图叫做边的双连通子图。而当子图的边数达到最大时,叫做边的双连通分量。原理是图中所有割边再求一次 SCC,可直接使用求 SCC 的代码。

对于一个无向图的子图,当删除其中任意一个点后,不改变图内点的连通性,这样的子图叫做点的双连通子图。而当子图的边数达到最大时,叫做点的双连通分量。下面给出求点双连通分量的代码。

struct BiconnectedConnectedComponenet : Graph
{
	vector<int> dep, bid, stak, cutPoint, cutEdge; //bid边的端点所属双连通块
	BiconnectedConnectedComponenet(int n) : Graph(n) {}
	void ask()
	{
		dep.assign(v.size(), v.size());
		bid.assign(e.size(), e.size());
		cutPoint.assign(v.size(), 0);
		cutEdge.assign(e.size(), 0);
		for (int i = 0; i < v.size(); ++i)
			if (dep[i] == v.size())
				dfs(i, v.size());
	}
	int dfs(int u, int fa)
	{
		int low = dep[u] = fa != v.size() ? dep[fa] + 1 : 0;
		for (int i = 0, k, to, lowto; i < v[u].o.size(); ++i)
			if (k = v[u].o[i], to = e[k].second, to != fa)
			{
				if (dep[to] == v.size())
				{
					stak.push_back(k);
					low = min(low, lowto = dfs(to, u));
					if (lowto > dep[u])
						cutEdge[k] = cutEdge[k ^ 1] = 1;
					if (lowto >= dep[u])
						for (cutPoint[u] = fa != v.size() || i;;)
						{
							int x = stak.back();
							stak.pop_back();
							bid[x] = bid[x ^ 1] = k;
							if (x == k)
								break;
						}
				}
				else if (dep[to] < dep[u])
				{
					stak.push_back(k);
					low = min(low, dep[to]);
				}
			}
		return low;
	}
};

双连通图的构造

先求出所有的桥,然后删除这些桥边,剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点,再把桥边加回来,最后的这个图一定是一棵树,边连通度为 1。统计出树中度为 1 的节点的个数,即为叶节点的个数,记为leaf。至少在树上添加(leaf+1)/2条边,就能使树达到边双连通:先把两个最近公共祖先最远的两个叶节点之间连接一条边,这样可以把这两个点到祖先的路径上所有点收缩到一起,因为一个形成的环一定是双连通的;然后再找两个最近公共祖先最远的两个叶节点,这样一对一对找完,恰好是(leaf+1)/2次,把所有点收缩到了一起。

无向图求边双连通分量&有向图求强连通分量

无向图求边双连通分量

有向图求强连通分量

struct StronglyConnectedComponenet : Graph
{
	vector<int> dep, sid, stak; //sid=点所属连通块内一点
	StronglyConnectedComponenet(int n) : Graph(n) {}
	void ask()
	{
		dep.assign(v.size(), v.size());
		sid.assign(v.size(), v.size());
		for (int i = 0; i < v.size(); ++i)
			if (dep[i] == v.size())
				dfs(i, v.size());
	}
	int dfs(int u, int fa)
	{
		int low = dep[u] = fa != v.size() ? dep[fa] + 1 : 0;
		stak.push_back(u);
		for (int i = 0, k, to; i < v[u].o.size(); ++i)
			if (k = v[u].o[i], to = e[k].second, to != fa /*, 1*/) //求强连通分量把注释去掉,即允许走回边
			{
				if (dep[to] == v.size())
					low = min(low, dfs(to, u));
				else if (sid[to] == v.size())
					low = min(low, dep[to]);
			}
		if (low == dep[u])
			for (;;)
			{
				int x = stak.back();
				stak.pop_back();
				sid[x] = u;
				if (x == u)
					break;
			}
		return low;
	}
};

2-SAT

使用示例,n 个布尔变量$x_0\ldots x_{n-1}$,逻辑表达式$Y=(A_0+B_0)(A_1+B_1)\ldots(A_{m-1}+B_{m-1})$,其中$A_i,B_i\in{x_j,\overline{x_j}}$,判断是否存在$x_0\ldots x_{n-1}$的取值使得 Y 值为 1。因为$A+B=(\overline A\to B)(\overline B\to A)$,所以对于一个要求$A+B$,我们连$\overline A\to B,\overline B\to A$两条边。如果有一条边$A\to B$,意味着如果 A 成立那么 B 必然成立。若$\exists i,x_i,\overline{x_i}\in$同一 SCC,则不存在。

模板要求顶点数v.size()是偶数,ii ^ 1互为相反变量且奇数下标代表布尔变量为真的情况。最后输出结果在ok中。不满足对任意 iok[i] ^ ok[i ^ 1] == 1时,ask函数返回false

struct TwoSat : StronglyConnectedComponenet
{
	vector<int> ok;
	TwoSat(int n) : StronglyConnectedComponenet(n) {}
	void addOR(int a, int b) { add({a ^ 1, b}), add({b ^ 1, a}); }
	void addXOR(int a, int b) { addOR(a, b), addOR(a ^ 1, b ^ 1); }
	void addXNOR(int a, int b) { addOR(a, b ^ 1), addOR(a ^ 1, b); }
	int ask()
	{
		StronglyConnectedComponenet::ask();
		for (int i = 0; i < v.size(); i += 2)
			if (sid[i] == sid[i ^ 1])
				return 0;
		vector<vector<int>> g(v.size());
		vector<int> ind(v.size(), 0), cf(v.size(), 0), stak;
		for (int i = 0; i < v.size(); ++i)
		{
			cf[sid[i]] = sid[i ^ 1];
			for (int j = 0, k; j < v[i].o.size(); ++j)
				if (sid[e[k = v[i].o[j]].second] != sid[i])
					g[sid[e[k].second]].push_back(sid[i]), ++ind[sid[i]];
		}
		for (int i = 0; i < v.size(); ++i)
			if (sid[i] == i && !ind[i])
				stak.push_back(i);
		for (ok.assign(v.size(), -1); !stak.empty();)
		{
			int u = stak.back();
			stak.pop_back();
			if (ok[u] < 0)
				ok[u] = 1, ok[cf[u]] = 0;
			for (int i = 0; i < g[u].size(); ++i)
				if (!--ind[g[u][i]])
					stak.push_back(g[u][i]);
		}
		for (int i = 0; i < v.size(); ++i)
			if (i != sid[i])
				ok[i] = ok[sid[i]];
		return 1;
	}
};
2-SAT 暴力搜索求字典序最小的解

使用示例,时间复杂度最坏为为$O(VE)$。

struct TwoSat : Graph
{
	vector<int> ok;
	TwoSat(int n) : Graph(n) {}
	void addOR(int a, int b) { add({a ^ 1, b}), add({b ^ 1, a}); }
	void addXOR(int a, int b) { addOR(a, b), addOR(a ^ 1, b ^ 1); }
	void addXNOR(int a, int b) { addOR(a, b ^ 1), addOR(a ^ 1, b); }
	int dfs(int u, vector<int> &stak)
	{
		if (ok[u ^ 1])
			return 0;
		if (ok[u])
			return 1;
		ok[u] = 1;
		stak.push_back(u);
		for (int i = 0; i < v[u].o.size(); ++i)
			if (!dfs(e[v[u].o[i]].second, stak))
				return 0;
		return 1;
	}
	int ask()
	{
		ok.assign(v.size(), 0);
		for (int i = 0; i < v.size(); i += 2)
			if (!ok[i] && !ok[i ^ 1])
			{
				vector<int> stak;
				if (!dfs(i, stak))
				{
					for (int j = 0; j < stak.size(); ++j)
						ok[stak[j]] = 0;
					if (!dfs(i ^ 1, stak))
						return 0;
				}
			}
		return 1;
	}
};

二分图

二分图的一个等价定义是:不含有含奇数条边的环的图。

完美匹配图中所有的顶点都是匹配点。

二分图的最小点覆盖(最小割)是指最少的顶点数使得二分图 G 中的每条边都至少与其中一个点相关联。二分图中,最小割=最大匹配。

二分图的最小边覆盖(最大独立集)是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图中,最小点覆盖+最小边覆盖=总点数。

Hall 定理:二分图中的两部分顶点组成的集合分别为 X,Y ,则有一组无公共点的边,一端恰好为组成 X 的点的充分必要条件是:X 中的任意 k 个点至少与 Y 中的 k 个点相邻。对于区间图只需要考虑极端情况,线段树维护。

关键点:一定在最大匹配中的点。 求出任意一个最大匹配,那么只需要考虑哪些匹配点不一定在。 假设是考虑左侧的点,右侧类似: 将匹配边从右往左,非匹配边从左到右,从左侧每个未匹配点开始 DFS 到的匹配点都不是关键点。

关键边:求出任意一个最大匹配,将匹配边从右到左,剩余边从左到右,求出 SCC。 对于一条边:若它位于当前匹配中,那么若两端点位于同一 SCC,则是可能在,否则必定在;若它不位于当前匹配中,那么若两端点位于同一 SCC,则是可能在,否则必定不在。

Hungary 求最大匹配

使用示例

左边 nl 个点$0\ldots nl-1$,右边 nr 个点$0\ldots nr-1$,取n=max(nl,nr),左 i 右 j 间相连则g[i].push_back(j);

生成fl[i]表示左边第 i 个匹配右边第fl[i]个,fr同理。时间复杂度$O(n^3)$。未匹配的值为fl[i] == N。匹配是一个边集,其中任意两条边都没有公共顶点;扫一遍flfr判断有多少不等于N即为最大匹配数。

struct Hungary
{
	vector<int> g[N];
	int n, fl[N], fr[N], vr[N];
	int dfs(int x, int rt)
	{
		for (auto y : g[x])
			if (vr[y] != rt)
				if (vr[y] = rt, fr[y] == N || dfs(fr[y], rt))
					return fl[fr[y] = x] = y, 1;
		return 0;
	}
	void ask()
	{
		fill(fl, fl + n, N), fill(fr, fr + n, N), fill(vr, vr + n, N);
		for (int i = 0; i < n; ++i)
			if (fl[i] == N)
				dfs(i, i); //找完全匹配时如果返回值为0可直接return
	}
};

HopcroftKarp 求最大匹配

使用示例,时间复杂度$O(\sqrt{\vert V\vert }\vert E\vert )$,稀疏图上效果明显。

struct HopcroftKarp
{
	vector<int> g[N];
	int n, fl[N], fr[N], hl[N], hr[N], q[N];
	bool dfs(int x)
	{
		int c = hl[x] + 1, y = hl[x] = N;
		for (auto y : g[x])
			if (hr[y] == c)
				if (hr[y] = N, fr[y] == N || dfs(fr[y]))
					return fl[fr[y] = x] = y, 1;
		return 0;
	}
	void ask()
	{
		fill(fl, fl + n, N), fill(fr, fr + n, N);
		for (int x = 0; x < n; ++x)
			for (auto y : g[x])
				if (fr[y] == N)
				{
					fl[fr[y] = x] = y;
					break;
				}
		for (int ql, qr, ok;;)
		{
			fill(hl, hl + n, N), fill(hr, hr + n, N);
			for (int x = ql = qr = ok = 0; x < n; ++x)
				if (fl[x] == N)
					hl[q[qr++] = x] = 0;
			while (ql < qr)
				for (auto y : g[q[ql++]])
					if (hr[y] == N)
					{
						hr[y] = hl[q[ql - 1]] + 1;
						if (fr[y] == N)
							ok = 1;
						else if (hl[fr[y]] == N)
							hl[q[qr++] = fr[y]] = hr[y] + 1;
					}
			if (!ok)
				return;
			for (int x = 0; x < n; ++x)
				if (fl[x] == N)
					dfs(x);
		}
	}
};

KuhnMunkres 求最优完备匹配

使用示例

左 x 右 y 代价a[x][y]。最大费用流时,a 初始化 0;最大费用最大流时,a 初始化-N*INF

struct KuhnMunkres
{
	ll a[N][N], hl[N], hr[N], slk[N];
	int n, fl[N], fr[N], vl[N], vr[N], pre[N], q[N], ql, qr;
	int check(int i)
	{
		if (vl[i] = 1, fl[i] != N)
			return vr[q[qr++] = fl[i]] = 1;
		while (i != N)
			swap(i, fr[fl[i] = pre[i]]);
		return 0;
	}
	void bfs(int s)
	{
		fill(slk, slk + n, INF), fill(vl, vl + n, 0), fill(vr, vr + n, 0);
		for (vr[q[ql = 0] = s] = qr = 1;;)
		{
			for (ll d; ql < qr;)
				for (int i = 0, j = q[ql++]; i < n; ++i)
					if (!vl[i] && slk[i] >= (d = hl[i] + hr[j] - a[i][j]))
						if (pre[i] = j, d)
							slk[i] = d;
						else if (!check(i))
							return;
			ll d = INF;
			for (int i = 0; i < n; ++i)
				if (!vl[i] && d > slk[i])
					d = slk[i];
			for (int i = 0; i < n; ++i)
			{
				if (vl[i])
					hl[i] += d;
				else
					slk[i] -= d;
				if (vr[i])
					hr[i] -= d;
			}
			for (int i = 0; i < n; ++i)
				if (!vl[i] && !slk[i] && !check(i))
					return;
		}
	}
	void ask()
	{
		fill(fl, fl + n, N), fill(fr, fr + n, N), fill(hr, hr + n, 0);
		for (int i = 0; i < n; ++i)
			hl[i] = *max_element(a[i], a[i] + n);
		for (int j = 0; j < n; ++j)
			bfs(j);
	}
};

带花树

一般图最大匹配

使用示例

struct Blossom : Graph
{
	vector<int> f;
	Blossom(int n) : Graph(n) {}
	void ask()
	{
		f.assign(v.size(), v.size());
		vector<int> vis(v.size());
		for (int s = 0, cnt = vis.back(); s < v.size(); ++s)
			if (f[s] == v.size())
			{
				UnionfindSet ufs(v.size());
				vector<int> pre(v.size(), v.size()), flag(v.size(), 2);
				for (deque<int> q(flag[s] = 1, s); !q.empty() && f[s] == v.size(); q.pop_front())
					for (int i = 0, x = q.front(), y, a, b; i < v[x].o.size(); ++i)
						if (y = e[v[x].o[i]].second, y != f[x] && flag[y] && ufs.ask(x) != ufs.ask(y))
						{
							if (flag[y] == 1)
							{
								for (a = x, b = y, ++cnt;; swap(a, b))
									if (a != v.size())
									{
										if (vis[a = ufs.ask(a)] == cnt)
											break;
										vis[a] = cnt, a = f[a] != v.size() ? pre[f[a]] : v.size();
									}
								if (ufs.ask(x) != a)
									pre[x] = y;
								if (ufs.ask(y) != a)
									pre[y] = x;
								for (int p[2] = {x, y}, j = 0; j < 2; ++j)
									for (int x = p[j], y, z; x != a; ufs.merge(y, x), ufs.merge(x = z, y))
									{
										if (ufs.ask(z = pre[y = f[x]]) != a)
											pre[z] = y;
										if (!flag[y])
											flag[y] = 1, q.push_back(y);
										if (!flag[z])
											flag[z] = 1, q.push_back(z);
									}
							}
							else if (f[y] != v.size())
								pre[y] = x, flag[y] = 0, flag[f[y]] = 1, q.push_back(f[y]);
							else
							{
								for (pre[y] = x; y != v.size();)
									swap(y, f[f[y] = pre[y]]);
								break;
							}
						}
			}
	}
};

树形图

最小生成树

无向图

同时给出 Prim 算法(生成新树)、Kruskal 算法(消耗小)。

struct Prim : Graph
{
	struct DisGreater
	{
		bool operator()(const Edge &e1, const Edge &e2)
		{
			return e1.len > e2.len;
		}
	};
	ll ans;
	vector<int> vis;
	priority_queue<Edge, vector<Edge>, DisGreater> q;
	Prim(const Graph &g, int root) : Tree(n), ans(0), vis(g.v.size(), 0) //生成新树,每条边都要有等长反向边
	{
		for (insert(root, g); !q.empty();)
		{
			Edge ed = q.top();
			if (q.pop(), !vis[ed.second])
				insert(ed.second, g), ans += ed.len, add(ed);
		}
	}
	void insert(int u, const Graph &g) //把点和对应的相连的边加入集合
	{
		vis[u] = 1;
		for (int i = 0, k; i < g.v[u].o.size(); ++i)
			if (k = g.v[u].o[i], !vis[g.e[k].second])
				q.push(g.e[k]);
	}
};
ll kruskal(vector<Edge> &e, int n) //会清空边集e,每条边被认作无向边
{
	ll ret = 0;
	UnionFindSet ufs(n);
	for (sort(e.begin(), e.end(), DisGreater()); !e.empty(); e.pop_back())
		if (ufs.fa(e.back().from) != ufs.fa(e.back().to))
		{
			ufs.merge(e.back().from, e.back().to);
			ret += e.back().len;
		}
	return /*ufs.siz>1?INF:*/ ret; //视情况选择去注释
}

有向图

使用示例

指定以 root 为根,如果没有限定根那么新建一个虚拟点作为根,向所有边连边长最大边长+1的边,在最后生成的图中去掉此边。时间复杂度$O(VE)$。

ll zhuLiu(vector<Edge> &e, int root, int n) //不存在返回INF
{
	for (ll ret = 0;;)
	{
		vector<ll> in(n, INF);
		vector<int> pre(n, n);
		for (int i = 0, to; i < e.size(); ++i)
		{
			if (e[i].first == (to = e[i].second))
				swap(e[i--], e.back()), e.pop_back();
			else if (in[to] > e[i].len)
				in[to] = e[i].len, pre[to] = e[i].first;
		}
		for (int i = in [root] = 0; i < n; ++i)
			if (in[i] == INF)
				return INF;
		vector<int> id(n, n), vis(n, n);
		int tn = 0;
		for (int i = 0, v; i < n; ++i)
		{
			for (ret += in [v = i]; vis[v] != i && id[v] == n && v != root; v = pre[v])
				vis[v] = i;
			if (v != root && id[v] == n)
			{
				for (int u = pre[v]; u != v; u = pre[u])
					id[u] = tn;
				id[v] = tn++;
			}
		}
		if (!tn)
			return ret;
		for (int i = 0; i < n; ++i)
			if (id[i] == n)
				id[i] = tn++;
		for (int i = 0, v; i < e.size(); ++i)
			if ((e[i].first = id[e[i].first]) != (e[i].second = id[v = e[i].second]))
				e[i].len -= in[v];
		n = tn, root = id[root];
	}
}

树链剖分与 LCA

使用示例

struct Diagram : Graph
{
	Fenwick data; //暂用树状数组作为默认数据结构
	Diagram(const Graph &g, int root) : Graph(g.v.size()), data(g.v.size())
	{
		build(root, g);
		int cnt = v[root].dfn = v[root].dep = 1;
		dfs(v[root].top = root, cnt);
	}
	void build(int u, const Graph &g) //无向图dfs建树,且重边在最前,u为根节点
	{
		v[u].siz = 1;
		for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
			if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz) //没访问过的点siz默认0
			{
				build(to, g);
				v[u].siz += v[to].siz;
				Graph::add(g.e[k]);
				if (v[ch(u)].siz < v[to].siz) //重边移到最前
					swap(v[u].o.front(), v[u].o.back());
			}
	}
	void dfs(int u, int &cnt)
	{
		for (int i = 0, to; i < v[u].o.size(); ++i)
		{
			v[to = ch(u, i)].dfn = ++cnt;
			v[to].top = i ? to : v[u].top;
			v[to].dep = v[u].dep + 1;
			dfs(to, cnt);
		}
	}
	int lca(int x, int y)
	{
		for (; v[x].top != v[y].top; x = fa(v[x].top))
			if (v[v[x].top].dep < v[v[y].top].dep)
				swap(x, y);
		if (v[x].dep < v[y].dep)
			swap(x, y);
		return y;
	}
	ll ask(int x, int y)
	{
		ll ans = 0;
		for (; v[x].top != v[y].top; x = fa(v[x].top))
		{
			if (v[v[x].top].dep < v[v[y].top].dep)
				swap(x, y);
			ans += data.ask(v[v[x].top].dfn, v[x].dfn);
		}
		if (v[x].dep < v[y].dep)
			swap(x, y);
		return ans += data.ask(v[y].dfn, v[x].dfn);
	}
	void add(int x, int y, ll pv)
	{
		for (; v[x].top != v[y].top; x = fa(v[x].top))
		{
			if (v[v[x].top].dep < v[v[y].top].dep)
				swap(x, y);
			data.add(v[v[x].top].dfn, v[x].dfn, pv);
		}
		if (v[x].dep < v[y].dep)
			swap(x, y);
		data.add(v[y].dfn, v[x].dfn, pv);
	}
};

点剖(点分治)

使用示例,零号点为虚节点。

struct TreeDiv : Graph
{
	int root;
	vector<int> mx, siz, vis;
	TreeDiv(int n) : Graph(n), mx(n, n), siz(n), vis(n) {}
	void dfsRoot(int u, int fa)
	{
		for (int i = mx[u] = siz[u] = 0, k, to; i < v[u].o.size(); ++i)
			if (k = v[u].o[i], to = e[k].second, to != fa && !vis[to])
				if (dfsRoot(to, u), siz[u] += siz[to], mx[u] < siz[to])
					mx[u] = siz[to];
		if (mx[u] < mx[0] - ++siz[u])
			mx[u] = mx[0] - siz[u];
		if (mx[root] >= mx[u])
			root = u;
	}
	void dfsDis(int u, int fa, ll d)
	{
		//用d更新答案
		for (int i = 0, k, to; i < v[u].o.size(); ++i)
			if (k = v[u].o[i], to = e[k].second, to != fa && !vis[to])
				dfsDis(to, u, d + e[k].len);
	}
	int cal(int u, ll d) //返回符合要求的点对数
	{
		return dfsDis(u, 0, d), /*得到答案*/;
	}
	void dfs(int u = 1)
	{
		dfsRoot(u, root = 0), ans += cal(u = root, 0), vis[u] = 1;
		for (int i = 0, k, to; i < v[u].o.size(); ++i)
			if (k = v[u].o[i], to = e[k].second, !vis[to])
				ans -= cal(to, e[k].len), mx[0] = siz[to], dfs(to);
	}
};