[题解]CF1364-D Ehab's Last Corollary

Posted on 2020-06-14 In 题解

很妙的一题

题意

给出 $n$ 个节点 $m$ 条边的无向连通图和参数 $k$ ,求:

严格 $⌈ \frac{k}{2} ⌉$ 大小的点独立集
或大小 $k$ 的简单环

$3 \leq k \leq n \leq 10^{5}, n - 1 \leq m \leq 2 \cdot 10^{5}$

思路

解法1

我们求出一个原图的DFS树,当某个节点 $u$ 存在反向边时,找出终点 $v$ 深度最深的反向边.容易看出这个反向边在一个简单环中,且这个简单环不会被其他边分割.如果这个环的大小 $\leq k$ ,直接输出即可,否则我们取不相邻的 $⌈ \frac{k}{2} ⌉$ 个点,它们形成一个点独立集.

如果原图无环(或者说是一棵树),那么我们很容易就能求出大小 $⌈ \frac{k}{2} ⌉$ 的点独立集.

解法2

我们求出任意一个环,然后枚举所有的边 $1. . . m$ .如果某条边把这个环分割开(即起点终点都在环上),那么保留这个环的任意一半,继续该过程.最后我们会得到一个不被其他边分割的简单环.之后的处理同解法1.

如果原图是一棵树,同解法1.

(比赛时我用的就是这种做法,但是写T了=-=个人觉得这是最难想也最难写的做法,鬼知道我当时在干什么)

解法3

(来自Um_nik的代码)https://codeforces.com/contest/1364/submission/83636767

%%%%%

根据原题,无论我们求点独立集还是简单环,都需要最多 $k$ 个点,那么我们简单粗暴地把所有编号$ > k $的点删掉, 再在剩下的图 (* * 注意新图可能不连通 * *) 中寻找环 . 如果我们找到任意一个环, 直接输出即可, 因为这个环的大小肯定$ k $. 如果没有环 (新图是一个森林), 那也能很容易地找到$ $大小的点独立集.

代码

//D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5+10;
const int maxm = 4e5+10;
struct Edge{
	int from,to,next,cnt;
	Edge(int from = 0,int to = 0,int next = 0):from(from),to(to),next(next){}
}edge[maxn];
int head[maxn],cnt,d,dep[maxn],p[maxn];
bool vis[maxn],col[maxn];
void addedge(int f,int t){
	edge[cnt] = Edge(f,t,head[f]);
	head[f] = cnt++;
}
int n,m,k;
void DFS(int u){
	if(vis[u])return;
	vis[u] = 1;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].to;
		if(vis[v] and dep[v] > dep[u]){
			vector<int>cir = {};
			int cur = v;
			while(cur != u){
				cir.push_back(cur);
				cur = p[cur];
			}
			cir.push_back(u);
			int s = cir.size();
			cout << 2 << endl << s << endl;
			for(int yay:cir)cout << yay << " ";
			exit(0);
		}
		else if(!vis[v]){
			p[v] = u;
			dep[v] = dep[u]+1;
			col[v] = !col[u];
			DFS(v);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	memset(head,-1,sizeof(head));
	cin >> n >> m >> k;
	d = ceil((double)k/2);
	for(int i = 1;i <= m;i++){
		int f1,t1;
		cin >> f1>> t1;
		if(f1 > k or t1 > k)continue;
		addedge(f1,t1);
		addedge(t1,f1);
	}
	int cnt1 = 0; 
	for(int i = 1;i <= n;i++)DFS(i);
	vector<int>ans = {};
	for(int i = 1;i <= n;i++)if(col[i])cnt1++;
	int qwq = 0;
	if(cnt1 >= d)qwq = 1;
	for(int i = 1;i <= n;i++)if(col[i] == qwq){
		if((int)ans.size() == d)break;
		ans.push_back(i);
	}
	cout << 1 << endl;
	for(int x:ans)cout << x << " ";
	return 0;
}

[题解]UVA11107 Life Forms

Posted on 2020-06-08 In 题解

题面:

https://vjudge.net/problem/UVA-11107

思路

这里给出一种字符串Hash+二分的做法.

对每个字符串分别进行Hash,再二分最长子串的长度 $L$ .在判断 $L$ 是否合法时,只需求出每个字符串中长度为 $L$ 的不重复子串,再统计全部字符串中所有子串的个数.如果有子串出现次数大于等于 $\frac{n}{2} + 1$ ,那么 $L$ 合法.

实现上,使用map进行统计( $c n t$ )和判重( $v i s$ ).对每个字符串 $s$ ,计算以 $[1. . . | s | - L + 1]$ 为起点,长度为 $L$ 的子串的hash值 $h_{i}$ ,去重后添加到 $c n t$ 里.在添加过程中如果有 $c n t [h_{i}] \geq \frac{n}{2} + 1$ 那么 $L$ 合法,同时将该段子串添加到答案中.输出时对答案去重输出即可,同时注意UVA的毒瘤格式要求=-=

这个做法时间效率很低(在不作优化的情况下跑了3.72s),但是比较好想和好写

代码

//UVA11107
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3+10,maxs = 105;
const ull x = 13331;
int n;
ull xp[maxn],H[maxn][maxs];
string raw[maxs];
vector<string>ans;
bool check(int L){
	bool ok = 0;
	map<ull,int>cnt;
	for(int k = 1;k <= n;k++){
		map<ull,bool>vis;
		for(int i = 1;i+L-1 <= raw[k].size();i++){
			ull u = H[i+L-1][k] - H[i-1][k]*xp[L];
			if(!vis[u]){
				vis[u] = 1;
				cnt[u]++;
				if(cnt[u] >= n/2+1)ok = 1;
			}
		}
	}
	return ok;
}
void solve(int L){
	map<ull,int>cnt;
	for(int k = 1;k <= n;k++){
		map<ull,bool>vis;
		for(int i = 1;i+L-1 <= raw[k].size();i++){
			ull u = H[i+L-1][k] - H[i-1][k]*xp[L];
			if(!vis[u]){
				vis[u] = 1;
				cnt[u]++;
				if(cnt[u] >= n/2+1){
					string yay = "";
					for(int j = i;j <= i+L-1;j++)yay += raw[k][j-1];
					ans.push_back(yay);
				}
			}
		}
	}
	return;
} 
int main(){
	xp[0] = 1;
	for(int i = 1;i < maxn;i++)xp[i] = xp[i-1]*x;
	bool wtf = 0; 
	while(scanf("%d",&n) == 1 and n){
		if(wtf)cout << endl;
		wtf = 1;
		ans.clear();
		for(int i = 1;i <= n;i++){
			string u;
			cin >> u;
			raw[i] = u;
			for(int j = 1;j <= u.size();j++)H[j][i] = H[j-1][i]*x + u[j-1] - 'a';
		}
		int L = 1,R = maxn,M,len = 0;
		while(L <= R){
			M = (L+R)/2;
			if(check(M)){
				len = M;
				L = M+1;
			}
			else R = M-1;
		}
		solve(len);
		sort(ans.begin(),ans.end());
		if(ans.size() and len){
			for(int i = 0;i < ans.size();i++)if(!i or ans[i] != ans[i-1])cout << ans[i] << endl;
		}
		else cout << "?\n";
	}
	return 0;
}

[题解]CF1355C-Count Triangles

Posted on 2020-05-16 In 题解

写这个不是因为这题多难或者有意思,纯粹是纪念一下自己有多傻逼=-=

题意

给出 $A, B, C, D$ 求满足 $A \leq x \leq B \leq y \leq C \leq z \leq D$ ,的 $x, y, z$ 能组成的三角形个数

$1 \leq A \leq B \leq C \leq D \leq 5 e 5$

思路

很显然只要满足 $z < x + y$ 且 $C \leq z \leq D$ 就行=-=

那么枚举 $x$ ,把 $[x + B, x + C]$ 加1(用前缀和维护一下就行),再枚举 $z$ 统计满足 $z < x + y$ 的个数就行=-=

复杂度 $O (C)$

就这玩意都做不出来,我是傻逼

代码

//C 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
typedef long long ll;
int pre[maxn];
int main(){
	ll a,b,c,d,ans = 0;
	cin >> a >> b >> c >> d;
	for(int i = a;i <= b;i++)pre[i+b]++,pre[i+c+1]--;
	for(int i = 1;i < maxn;i++)pre[i] += pre[i-1];
	for(int i = 0;i < maxn;i++)ans += pre[i]*max(0ll,min(d,(ll)(i-1)) - c + 1); 
	cout << ans;
	return 0;
}

[题解]CF1325E-Ehab's REAL Number Theory Problem

Posted on 2020-05-15 Edited on 2020-05-21 In 题解

一道有意思的毒瘤题

题意

给出数列 ${a_{1}, a_{2}, . . ., a_{n}}$ ,其中每个 $a_{i}$ 最多只有7个因子.求乘积为完全平方数的最短子序列

$1 \leq n \leq 1 e 5$ , $1 \leq a_{i} \leq 1 e 6$

思路

首先条件里"最多只有7个因子"是很有意思的一个提示,它实际上是指每个数最多只有2个素因子

证明:

我们考虑因子个数定理:

以 $d (N)$ 表示 $N$ 的因子个数,且 $N = Σ_{i = 1}^{n} p_{i}^{k_{i}}$

则有 $d (N) = \prod_{i = 1}^{n} (k_{i} + 1)$

容易看出当 $N$ 有3个素因子时, $d (N) \geq 8$ .故N最多只有两个素因子.

如此可以分解每个 $a_{i}$ 为 $a_{i} = p^{k_{1}} q^{k_{2}}$ 的形式.因为我们需要求完全平方数, $k_{1}, k_{2}$ 可以直接模2.之后有如下三种情况:

$a_{i} = 1$
$a_{i} = 1 * p_{i}$
$a_{i} = p_{i} * q_{i}$ 我们要做的就是保证子序列里每个 $p_{i}, q_{i}$ 的指数为偶数,同时使这个序列最短.

如何高效求解这个问题?上面的因子分解得到了 $p, q$ 两个因子,让人联想到图的连边.不妨如此建模:将因子作为点,向 $a_{i}$ 的两个因子 $p_{i}, q_{i}$ 连一条无向无权边,则问题转化为求这个图里的最小环.(因为一个简单环里每个点的度数都为2,满足每个因子的指数都为偶数这一要求).

对于无向无权图图求最小环我们可以简单地对每个点做BFS.对于一条未访问的边 $u, v$ ,如果 $v$ 已访问过,那么该图存在一个长度为 $d i s [u] + d i s [v] + 1$ 的环(请自己画图验证).但是这样复杂度为 $O (n^{2})$

考虑这个图的特殊性质:任意正整数 $N$ 最多只有一个大于 $\sqrt{N}$ 的素因子,换句话说这个图里每条边都至少有一个点标号小于 $\sqrt{m a x {a_{i}}}$ .只需枚举这些点即可.

总复杂度: $O (\sqrt{m a x a_{i}} n)$

代码

//CF1325E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
const int maxm = 1e7+10;
struct Edge{
	int f,t,next;
	Edge(int f = 0,int t = 0,int next = 0):f(f),t(t),next(next){}
}edge[maxn];
int cnt,head[maxn],dis[maxn],ans = 1e9;
void addedge(int f,int t){
	edge[cnt] = Edge(f,t,head[f]);
	head[f] = cnt++;
}
void add(int f,int t){
	addedge(f,t);
	addedge(t,f);
}
bool visp[maxn],vis[maxn];
vector<int>P,d[maxn];
int n,raw[maxn];
void init(){
	visp[1] = 1;
	for(int i = 2;i < maxn;i++)if(!visp[i]){
		for(int j = i*2;j < maxn;j+=i)visp[j] = 1;
	}
	for(int i = 2;i < maxn;i++)if(!visp[i]){
		P.push_back(i);
	}
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> raw[i];
		int cur = raw[i];
		if(!visp[cur]){
			d[i].push_back(cur);
			continue;
		}
		for(int j = 2;j*j <= raw[i];j++){
			int cnt2 = 0;
			while(cur%j == 0){
				cur /= j;cnt2++;
			}
			if(cnt2%2)d[i].push_back(j);
		}
		if(cur > 1)d[i].push_back(cur);
	}
	for(int i = 1;i <= n;i++){
		if(!d[i].size()){
			cout << 1;
			exit(0);
		}
		else if(d[i].size() == 1){
			add(1,d[i][0]);
		}
		else add(d[i][0],d[i][1]);
	}
}
void BFS(int s){
	memset(dis,-1,sizeof(dis));
	dis[s] = 0;
	queue<pair<int,int> >q;
	q.push(make_pair(s,0));
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		int u = now.first,fa = now.second;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t;
			if(v == fa)continue;
			if(dis[v] == -1){
				dis[v] = dis[u]+1;
				q.push(make_pair(v,u));
			}
			else{
				ans = min(ans,dis[v]+dis[u]+1);
			}
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	init();
	for(int i = 1;i <= 1010;i++)BFS(i);
	if(ans == 1e9)ans = -1;
	cout << ans;
	return 0;
}

$2^{2 n - 1} + 2^{2 n - 2} - 2^{n}$

Mobius-Transformation

Posted on 2020-05-13 Edited on 2021-05-03 In 笔记

这个菜鸡现在还什么都不会>_>慢慢更新吧

前置知识

整除分块

设 $f (x) = ⌊ \frac{k}{x} ⌋$

$f (x)$ 分布呈块状,对于任意一个 $i$ ,有最大的 $j = ⌊ \frac{k}{⌊ \frac{k}{i} ⌋} ⌋$ ,使得 $f (i) == f (i + 1) == . . . = f (j)$

对于类似 $\sum_{i = 1}^{n} ⌊ \frac{k}{i} ⌋$ 的式子,可分块在 $O (\sqrt{n})$ 时间内计算完毕

代码:

for(int l = 1;l <= n;l = r+1){
		if(k/l)r = min(n,k/(k/l));
		else r = n;
		ans += (r-l+1)*(k/l);
	}

狄利克雷(Dirichlet)卷积

定义

设 $f, g$ 为两个数论函数,其狄利克雷卷积 $f * g$ 为: $f * g (n) = \sum_{d | n} f (d) g (\frac{n}{d})$

常用式子

\begin{aligned} ε = μ * 1 & ⟺ ε (n) = \sum_{d ∣ n} μ (d) \\ d = 1 * 1 & ⟺ d (n) = \sum_{d ∣ n} 1 \\ σ = id * 1 & ⟺ σ (n) = \sum_{d ∣ n} d \\ φ = μ * id & ⟺ φ (n) = \sum_{d ∣ n} d \cdot μ (\frac{n}{d}) \end{aligned}

常用结论

$\sum_{d | n}^{n} φ (d) = n$

$[gcd (i, j) == 1] = ϵ (gcd (i, j) = \sum_{d | gcd (i, j)} μ (d)$

套路题

$\sum_{i = 1}^{n} g c d (i, n)$

$\begin{aligned} \sum_{i = 1}^{n} gcd (i, n) \\ = \sum_{d | n} d \sum_{i = 1}^{n} [gcd (i, n) == d] \\ = \sum_{d | n} d \sum_{i = 1}^{\frac{n}{d}} [gcd (i, n) == 1] \\ = \sum_{d | n} d \cdot φ (\frac{n}{d}) \end{aligned}$

$\sum_{i = 1}^{n} \sum_{j = 1}^{n} gcd (i, j)$

$\begin{aligned} \sum_{i = 1}^{n} \sum_{j = 1}^{n} gcd (i, j) \\ = \sum_{d = 1}^{n} d \sum_{i = 1}^{n} \sum_{j = 1}^{n} [g c d (i, j) == d] \\ = \sum_{d = 1}^{n} d \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^{\frac{n}{d}} [g c d (i, j) == 1] \\ = \sum_{d = 1}^{n} d (2 \cdot \sum_{i = 1}^{\frac{n}{d}} φ (i) - 1) \end{aligned}$

关于最后一步,我们设 $f (x) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} [g c d (i, j) == 1]$

手画一下,容易看出 $f (x) = 2 \cdot \sum_{i = 1}^{n} φ (i) - 1$

另一种做法:

我们知道 $φ$ 有这么一个性质, $\sum_{d | n}^{n} φ (d) = n$

也就是 $\sum_{d | gcd (i, j)}^{n} φ (d) = gcd (i, j)$

那么: $\begin{aligned} \sum_{i = 1}^{n} \sum_{j = 1}^{n} gcd (i, j) \\ = \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{d | gcd (i, j)} φ (d) \\ = \sum_{d = 1}^{n} φ (d) \sum_{i = 1}^{n} [d | i] \sum_{j = 1}^{n} [d | j] \\ = \sum_{d = 1}^{n} φ (d) \cdot ⌊ \frac{n}{d} ⌋ ⌊ \frac{m}{d} ⌋ \end{aligned}$ 少处理个前缀和=-=而且我感觉这个做法更好理解

例题:洛谷P2398

$\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} gcd (i, j)$

和上面那个基本一样 $\begin{aligned} \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} gcd (i, j) \\ = \sum_{d = 1}^{n} d \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} [g c d (i, j) == d] \\ = \sum_{d = 1}^{n} d \sum_{i = 1}^{\frac{n}{d}} \sum_{j = i + 1}^{\frac{n}{d}} [g c d (i, j) == 1] \\ = \sum_{d = 1}^{n} d (\sum_{i = 1}^{\frac{n}{d}} φ (i) - 1) \end{aligned}$ (最后一步的化简和上一题大同小异,手画一下就有了)

$\sum_{i = 1}^{n} \sum_{i = 1}^{m} [gcd (i, j) == 1]$

前置知识: $ϵ (n) = \sum_{d | n} μ (d) = {\begin{cases} 1 & n = 1 \\ 0 & o t h e r w i s e \end{cases}$

开始愉快地推式子: $\begin{aligned} \sum_{i = 1}^{n} \sum_{i = 1}^{m} [gcd (i, j) == 1] \\ = \sum_{i = 1}^{n} \sum_{i = 1}^{m} ϵ (gcd (i, j)) \\ = \sum_{i = 1}^{n} \sum_{i = 1}^{m} \sum_{d | g c d (i, j)} μ (d) \\ = \sum_{d = 1}^{min (n, m)} μ (d) \sum_{i = 1}^{n} [d | i] \sum_{j = 1}^{m} [d | j] \\ = \sum_{d = 1}^{min (n, m)} μ (d) ⌊ \frac{n}{d} ⌋ ⌊ \frac{m}{d} ⌋ \end{aligned}$ 同理,我们有: $\sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} [gcd (i, j, k) == 1] = \sum_{d = 1}^{n} μ (d) (⌊ \frac{n}{d} ⌋)^{3}$

[题解] CF906D-Power Tower

Posted on 2020-05-13 Edited on 2021-03-09 In 题解

题意

给定序列 $w_{1}, w_{2}, . . ., w_{n}$ 和 $q$ 组询问,对于每组询问,求

当然,需要对这个值膜 $m$

(hexo渲染多重幂有问题,只好放原题图片了)

$1 \leq n \leq 1 e 5$ , $1 \leq m \leq 1 e 9$ , $1 \leq q \leq 1 e 5$

思路

考虑扩展欧拉定理:

$a^{b} = {\begin{array}{lcl} a^{b} & b < φ (p) \\ a^{b mod φ (p) + φ (p)} & b \geq φ (p) \end{array}$

由于 $p \geq 2$ 时 $φ (p)$ 为偶数,故 $p = φ (p)$ 的下降速度是log级别的,换句话说经过最多 $l o g (p)$ 次迭代之后 $p$ 便会变为1.由于 $x mod 1 == 0$ ,我们在 $l == r$ 或者 $p == 1$ 时便可跳出递归,单组询问的复杂度为 $O (l o g p)$ ,可以接受

在具体实现时,应预处理出 $p, φ (p), φ (φ (p)), . . ., 1$ 来减少时间开销,同时修改快速幂来适应扩欧定理(upd函数),细节见代码

代码

//CF906D 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll raw[maxn],n,mod;
map<ll,ll>vis;
ll phi(ll x){
	int m = (ll)sqrt(x+0.5);
	ll tans = x;
	for(int i = 2;i <= m;i++)if(!(x%i)){
		tans = tans/i*(i-1);
		while(!(x%i))x /= i;
	}
	if(x > 1)tans = tans / x * (x-1);
	return tans;
}
inline ll upd(ll x,ll p){
	return x<p?x:x%p+p;
}
ll Pow(ll x,ll d,ll p){
	ll tans = 1;
	if(d == 0)return 1;
	ll a = Pow(x,d/2,p);
	tans = upd(a*a,p);
	if(d%2)tans = upd(tans*x,p); 
	return upd(tans,p);
}
ll cal(ll l,ll r,ll p){
	if(l == r or p == 1)return upd(raw[l],p);
	else return Pow(raw[l],cal(l+1,r,vis[p]),p);
}
int main(){
	cin >> n >> mod;
	ll qwq = mod;
	while(qwq != 1){
		vis[qwq] = phi(qwq);
		qwq = vis[qwq];
	}
	vis[1] = 1;
	for(int i = 1;i <= n;i++)cin >> raw[i];
	int q;
	cin >> q;
	while(q--){
		int l,r;
		cin >> l >> r;
		cout << cal(l,r,mod)%mod << endl;
	}
	return 0;
}

$f (n) = O (g (n)) \Rightarrow f (n) \leq c_{f} \cdot g (n) \Rightarrow \frac{1}{f (n)} \geq \frac{1}{c_{f} \cdot g (n)} \Rightarrow \frac{1}{g (n)} \leq c_{f} \cdot \frac{1}{f (n)} 对于 n >= n_{f} 故有 \frac{1}{g (n)} = O (\frac{1}{f (n)})$

[题解]CF1350C-Orac and LCM

Posted on 2020-05-13 In 题解

题目大意

给定集合 ${a_{1}, a_{2}, . . ., a_{n}}$ ,求 $g c d ({l c m ({a_{i}, a_{j}}) | i < j})$

$2 n 1 e 5$ , $1 \leq a_{i} \leq 2 e 5$

思路

考虑唯一分解定理:

$a = \prod_{1}^{n} p_{i}^{k_{i}}$

$b = \prod_{1}^{n} p_{i}^{g_{i}}$

对于 $g c d$ 和 $l c m$ ,我们有:

$g c d (a, b) = \prod_{1}^{n} p_{i}^{m i n (k_{i}, g_{i})}$

$l c m (a, b) = \prod_{1}^{n} p_{i}^{m a x (k_{i}, g_{i})}$

观察易得,对于答案中的每个质因子 $p_{i}$ ,它的指数 $k_{i}$ 为 ${a_{1}, . . ., a_{n}}$ 中 $p_{i}$ 第二小 的指数 $k$

我们预处理出 $i$ 的所有质因数 $p [i]$ ,将 $a_{i}$ 分解,用 $d [i] [j]$ 表示 $a_{j}$ 的质因子 $i$ 的指数,排序后扫一遍 $d [i]$ 即可得到答案

具体来说 $a n s * = {\begin{array}{lcl} i^{d [i] [0]} & d [i] . s i z e () == n - 1 \\ i^{d [i] [1]} & d [i] . s i z e () \geq n - 1 \\ 1 & o t h e r w i s e \end{array}$

代码

//C
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+10;
int raw[maxn];
int vis[maxn];
ll Pow(int x,int d){
	ll tans = 1;
	if(d == 0)return 1;
	ll a = Pow(x,d/2);
	tans = a*a;
	if(d%2)tans = tans*x; 
	return tans;
}
bool n_prime[maxn];
vector<int>p[maxn],d[maxn];
void prime(){
	for(int i = 2;i <maxn;i++){
		if(!n_prime[i]){
			p[i].push_back(i); 
			for(int j = i*2;j < maxn;j += i){
				n_prime[j] = 1;
				p[j].push_back(i);
			}
		}
	}
	n_prime[1] = 1;
}
int main(){
	prime();
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)cin >> raw[i];
	for(int i = 1;i <= n;i++){
		int u = raw[i];
		for(int x:p[u]){
			int yay = 0;
			while(u%x == 0){
				yay++;
				u /= x;
			}
			d[x].push_back(yay);
		}
	}
	ll ans = 1;
	for(int i = 2;i < maxn;i++){
		sort(d[i].begin(),d[i].end());
		if(d[i].size() == n-1){
			ans *= Pow(i,d[i][0]);
		}
		else if(d[i].size() > n-1)ans *= Pow(i,d[i][1]); 
	}
	cout << ans;
	return 0;
}

math-misc

Posted on 2020-05-11 Edited on 2020-05-12 In 数学

本篇仅记录一些杂乱的知识点留作日后整理,更多是作Markdown和 $L_{A} T^{E} X$ 的练习用

[模板]计算几何

Posted on 2020-05-09 Edited on 2022-06-17 In 模板

[TOC]

二维

起手式(待补充):

typedef long long ll;
typedef long double ld;
const double PI = 3.14159265358979; 
const int maxn = 1e5+10;
struct Point{
	ld x,y;
	Point(ld x = 0,ld y = 0):x(x),y(y){}
	Point operator + (Point B){return Point(x+B.x,y+B.y);}
	Point operator - (Point B){return Point(x-B.x,y-B.y);}
	Point operator * (ld w){return Point(x*w,y*w);}
	Point operator / (ld w){return Point(x/w,y/w);}
	Point Rotate_90_clock(){return Point(y,-x);}//顺时针旋转90°
	ld len2(){return x*x + y*y;}//长度的平方
	ld len(){return(sqrt(x*x + y*y));}
    bool operator < (const Point & A) const{
		return (x == A.x?y < A.y:x < A.x);
	}
}point[maxn];
struct Circle{
	Point O;
	ld R;
	Circle(Point O = Point(0,0),ld R = 0):O(O),R(R){}
	ld R2(){return R*R;}
};
typedef Point Vector;
ld Dot(Vector A,Vector B){
	return A.x*B.x + A.y*B.y;
}//点积
ld Cross(Vector A,Vector B){
	return A.x*B.y - A.y*B.x;
}//二维叉积
Point Line_inter(Point P0,Point V0,Point P1,Point V1){
	ld t = Cross(P1 - P0,V1)/Cross(V0,V1);
	return P0 + V0 * t;
}//返回两向量交点.P和V分别为向量起点终点*
Circle p2circle(Point A,Point B){
	Circle tans = Circle((A+B)/2,0);
	tans.R = (tans.O - A).len();
	return tans;
}//两点的外接圆
Circle p2circle(Point A,Point B,Point C){
	Circle tans = Circle(Line_inter((A+B)/2,(B - A).Rotate_90_clock(),(A+C)/2,(C - A).Rotate_90_clock()),0);
	tans.R = (tans.O - A).len();
	return tans;
}//三点共圆
typedef Point Vector;
inline double to_rad(double deg){
	return deg*(PI/180);
}
Vector Rotate(Vector A,double rad){//逆时针 
	return Vector(A.x*cos(rad) - A.y*sin(rad),A.x*sin(rad) + A.y*cos(rad));
}

点到直线及线段距离

ld LinePointDist(Point p,Point a,Point b){//点到直线
	Vector v1 = b-a,v2 = p-a;
	return fabs(Cross(v1,v2) / len(v1));
}
ld SegPointDist(Point p,Point a,Point b){//点到线段
	if(a == b)return len(p - a);
	Vector v1 = b-a,v2 = p-a,v3 = p-b;
	if(Dot(v1,v2) < eps)return len(v2);
	if(Dot(v1,v3) > eps)return len(v3);
	return LinePointDist(p,a,b);
}

按角度旋转点

设点 $A (x, y)$ 绕点 $R (x_{r}, y_{r})$ 逆时针旋转 $θ$ 弧度后得到点 $A^{'} (x^{'}, y^{'})$ , 则有: $x^{'} = (x - x_{r}) \cdot \cos (θ) - (y - y_{r}) \cdot \sin (θ) + x_{r} y^{'} = (x - x_{r}) \cdot \sin (θ) + (y - y_{r}) \cdot \cos (θ) + y_{r}$

void rotate(ld & x,ld & y,ld theta,ld rx,ld ry){
    ld nx = (x - rx)*cos(theta) - (y - ry)*sin(theta) + rx;
    ld ny = (x - rx)*sin(theta) + (y - ry)*cos(theta) + ry;
    x = nx,y = ny;
}

凸包

输入顶点, 返回凸包. raw为原顶点数组,hull为凸包顶点数组

vector<Point> ConvexHull(vector<Point>raw){
    if(raw.size() == 1)return raw;
	sort(raw.begin(),raw.end());
	int n = raw.size(),idx = 0;
	vector<Point>hull(2*n+10);
	for(int i = 0;i < n;i++){
		while(idx > 1 and Cross(hull[idx-1] - hull[idx-2],raw[i] - hull[idx-1]) <= 0)idx--;
		hull[idx++] = raw[i];
	}
	int k = idx;
	for(int i = n-2;i >= 0;i--){
		while(idx > k and Cross(hull[idx-1] - hull[idx-2],raw[i] - hull[idx-1]) <= 0)idx--;
		hull[idx++] = raw[i];
	}
	hull.resize(idx-1);
	return hull;
}

闵可夫斯基和

点集 $A, B$ 的闵可夫斯基和为 $C = {a + b | a \in A, b \in B}$

复杂度 $O (n)$

vector<Point> minkowski(vector<Point> & C1,vector<Point> & C2){
	int n = (int)C1.size(),m = (int)C2.size();
	vector<Point>s1(n),s2(m),A(n+m+10);
	for(int i = 0;i < n-1;i++)s1[i] = C1[i+1] - C1[i];
	s1[n-1] = C1[0] - C1[n-1];
	for(int i = 0;i < m-1;i++)s2[i] = C2[i+1] - C2[i];
	s2[m-1] = C2[0] - C2[m-1];
	int tot = 0;
	A[tot] = C1[0] + C2[0];
	int p1 = 0,p2 = 0;
	while(p1 < n and p2 < m){
		tot++;
		A[tot] = A[tot-1] + (Cross(s1[p1],s2[p2]) >= eps?s1[p1++]:s2[p2++]);
	}
	while(p1 < n){
		++tot;
		A[tot] = A[tot-1] + s1[p1++];
	}
	while(p2 <= m){
		++tot;
		A[tot] = A[tot-1] + s2[p2++];
	}
	A.resize(tot+1);
	return A;
}

多边形面积

_Point为多边形点集,n为顶点数

double PolyArea(Point * _Point,int n){
	double area = 0;
	for(int i = 2;i < n;i++){
		area += Cross(_Point[i] - _Point[1],_Point[i+1] - _Point[1]);
	}
	return area/2; 
}

最小圆覆盖

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5+10;
struct Point{
	ld x,y;
	Point(ld x = 0,ld y = 0):x(x),y(y){}
	Point operator + (Point B){return Point(x+B.x,y+B.y);}
	Point operator - (Point B){return Point(x-B.x,y-B.y);}
	Point operator * (ld w){return Point(x*w,y*w);}
	Point operator / (ld w){return Point(x/w,y/w);}
	Point Rotate_90_clock(){return Point(y,-x);}//顺时针旋转90°
	ld len2(){return x*x + y*y;}//长度的平方
	ld len(){return(sqrt(x*x + y*y));}
}point[maxn];
struct Circle{
	Point O;
	ld R;
	Circle(Point O = Point(0,0),ld R = 0):O(O),R(R){}
	ld R2(){return R*R;}
};
typedef Point Vector;
ld Dot(Vector A,Vector B){
	return A.x*B.x + A.y*B.y;
}//点积
ld Cross(Vector A,Vector B){
	return A.x*B.y - A.y*B.x;
}//二维叉积
Point Line_inter(Point P0,Point V0,Point P1,Point V1){
	ld t = Cross(P1 - P0,V1)/Cross(V0,V1);
	return P0 + V0 * t;
}//返回两向量交点.P和V分别为向量起点终点*
Circle p2circle(Point A,Point B){
	Circle tans = Circle((A+B)/2,0);
	tans.R = (tans.O - A).len();
	return tans;
}//两点的外接圆
Circle p2circle(Point A,Point B,Point C){
	Circle tans = Circle(Line_inter((A+B)/2,(B - A).Rotate_90_clock(),(A+C)/2,(C - A).Rotate_90_clock()),0);
	tans.R = (tans.O - A).len();
	return tans;
}//三点共圆
Circle Min_Cir_Cover(Point * point,int n){
	random_shuffle(point+1,point+n+1);
	Circle res;
	for(int i = 1;i <= n;i++){
		if((point[i] - res.O).len2() > res.R2()){
			res = Circle(point[i],0);
			for(int j = 1;j < i;j++){
				if((point[j] - res.O).len2() > res.R2()){
					res = p2circle(point[i],point[j]);
					for(int k = 1;k < j;k++){
						if((point[k] - res.O).len2() > res.R2()){
							res = p2circle(point[i],point[j],point[k]);
						}
					}
				}
			}
		}
	}
	return res;
}//最小圆覆盖,输入点集数组和点的数量,返回一个圆

判断点在凸包内部及边界

bool Left(Point P,Point A,Point B) {
	return Cross(B - A,P - A) > 0;
}
bool Right(Point P,Point A,Point B) {
	return Cross(P - A,B - A) > 0;
}
bool Point_in_Convex(Point P,vector<Point> & C){
	int n = C.size();
	if (Left(P,C[0],C[n - 1]) or Right(P,C[0],C[1]))return 0;
	int l = 1, r = n - 1;
	while (l < r - 1) {
		int m = (l + r) / 2;
		if (Left(P, C[0], C[m])) {
			l = m;
		}
		else {
			r = m;
		}
	}
	if (!Right(P, C[l], C[r]))return 1;
	return 0;
}

三维

起手式:

鸽子biss

叉乘写为矩阵形式

$\vec{a} \times \vec{b} = A^{*} \vec{b} = (\begin{array}{cccc} 0 & - z_{1} & y_{1} \\ z_{1} & 0 & - x_{1} \\ - y_{1} & x_{1} & 0 \end{array}) (\begin{array}{cccc} x_{2} \\ y_{2} \\ z_{2} \end{array})$

$A^{*}$ 称为dual martix

最小球覆盖

来自上交红书《ACM国际大学生程序设计竞赛-算法与实现》

下标从0开始

复杂度: $O (n)$

输入:

npoint 全局变量, 点的个数

pt 全局变量, 点的坐标

调用 smallest_ball()

输出:

res 全局变量, 球心坐标

radius 全局变量, 球的半径

//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn = 2e5+10;
double eps = 1e-9;
struct Tpoint{
	double x,y,z;
	Tpoint(double x = 0,double y = 0,double z = 0):x(x),y(y),z(z){}
};
int npoint,nouter;
Tpoint pt[maxn],outer[4],res;
double radius,tmp;
inline double dist(Tpoint p1,Tpoint p2){
	double dx = p1.x - p2.x,dy = p1.y - p2.y,dz = p1.z - p2.z;
	return (dx*dx + dy*dy + dz*dz);
}
inline double dot(Tpoint p1,Tpoint p2){
	return p1.x*p2.x + p1.y*p2.y + p1.z*p2.z;
}
void ball(){
	Tpoint q[3];double m[3][3], sol[3],L[3],det;
	res.x = res.y = res.z = radius = 0;
	switch(nouter){
		case 1: res = outer[0];break;
		case 2:
			res.x = (outer[0].x+outer[1].x)/2;
			res.y = (outer[0].y+outer[1].y)/2;
			res.z = (outer[0].z+outer[1].z)/2;
			radius = dist(res,outer[0]);
			break;
		case 3:
			for(int i = 0;i < 2;i++){
				q[i].x = outer[i+1].x - outer[0].x;
				q[i].y = outer[i+1].y - outer[0].y;
				q[i].z = outer[i+1].z - outer[0].z;
			}
			for(int i = 0;i < 2;i++)
				for(int j = 0;j < 2;j++)m[i][j] = dot(q[i],q[j])*2;
			for(int i = 0;i < 2;i++)sol[i] = dot(q[i],q[i]);
			if(fabs(det = m[0][0]*m[1][1] - m[0][1]*m[1][0])<eps)return;
			L[0] = (sol[0]*m[1][1] - sol[1]*m[0][1])/det;
			L[1] = (sol[1]*m[0][0] - sol[0]*m[1][0])/det;
			res.x = outer[0].x + q[0].x*L[0] + q[1].x*L[1];
			res.y = outer[0].y + q[0].y*L[0] + q[1].y*L[1];
			res.z = outer[0].z + q[0].z*L[0] + q[1].z*L[1];
			radius = dist(res,outer[0]);
			break;
		case 4:
			for(int i = 0;i < 3;i++){
				q[i].x = outer[i+1].x - outer[0].x;
				q[i].y = outer[i+1].y - outer[0].y;
				q[i].z = outer[i+1].z - outer[0].z;
				sol[i] = dot(q[i],q[i]);
			}
			for(int i = 0;i < 3;i++)
				for(int j = 0;j < 3;j++)m[i][j] = dot(q[i],q[j])*2;
			det = m[0][0] * m[1][1] * m[2][2]
				+ m[0][1] * m[1][2] * m[2][0]
				+ m[0][2] * m[2][1] * m[1][0]
				- m[0][2] * m[1][1] * m[2][0]
				- m[0][1] * m[1][0] * m[2][2]
				- m[0][0] * m[1][2] * m[2][1];
			if(fabs(det) < eps)return;
			for(int j = 0;j < 3;j++){
				for(int i = 0;i < 3;i++)m[i][j] = sol[i];
				L[j] = (m[0][0] * m[1][1] * m[2][2]
					+ m[0][1] * m[1][2] * m[2][0]
					+ m[0][2] * m[2][1] * m[1][0]
					- m[0][2] * m[1][1] * m[2][0]
					- m[0][1] * m[1][0] * m[2][2]
					- m[0][0] * m[1][2] * m[2][1]
					)/det;
				for(int i = 0;i < 3;i++)m[i][j] = dot(q[i],q[j])*2;
			}
			res = outer[0];
			for(int i = 0;i < 3;i++){
				res.x += q[i].x * L[i];
				res.y += q[i].y * L[i];
				res.z += q[i].z * L[i];
			}
			radius = dist(res,outer[0]);
	}
}
void minball(int n){
	ball();
	if(nouter < 4){
		for(int i = 0;i < n;i++){
			if(dist(res,pt[i]) - radius > eps){
				outer[nouter] = pt[i];
				++nouter;
				minball(i);
				--nouter;
				if(i > 0){
					Tpoint Tt = pt[i];
					memmove(&pt[1],&pt[0],sizeof(Tpoint)*i);
					pt[0] = Tt;
				}
			}
		}
	}
}
double smallest_ball(){
	radius = -1;
	for(int i = 0;i < npoint;i++){
		if(dist(res,pt[i]) - radius > eps){
			nouter = 1;
			outer[0] = pt[i];
			minball(i);
		}
	}
	return sqrt(radius);
}
signed main(){
	cin >> npoint;
	for(int i = 0;i < npoint;i++){
		int x,y,z;
		cin >> x >> y >> z;
		pt[i] = Tpoint(x,y,z);
	}
	printf("%.10lf",smallest_ball());
	return 0;
}

[模板]图论

Posted on 2020-05-09 Edited on 2022-12-01 In 模板

[TOC]

建图

const int maxn = 2e5+10;
const int maxm = maxn*2;
int head[maxn],pa[maxn];
bool vis[maxn];
struct Edge{
	int f,t,next;
	Edge(int f = 0,int t = 0,int next = 0):f(f),t(t),next(next){}	
}edge[maxm];
int tcnt,cnt;
void addedge(int f,int t){
	edge[cnt] = Edge(f,t,head[f]);
	head[f] = cnt++;
}

最短路

SPFA

void spfa(int s){
    queue<int>q;
    for(int i = 1;i <= n;i++)dis[i] = INF;
    q.push(s);
    vis[s] = 1;
    dis[s] = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u];~i;i = edge[i].next){
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].w){
                dis[v] = dis[u] + edge[i].w;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

SPFA优化

来自OI-Wiki

除了队列优化（SPFA）之外，Bellman-Ford 还有其他形式的优化，这些优化在部分图上效果明显，但在某些特殊图上，最坏复杂度可能达到指数级。

堆优化：将队列换成堆，与 Dijkstra 的区别是允许一个点多次入队。在有负权边的图可能被卡成指数级复杂度。
栈优化：将队列换成栈（即将原来的 BFS 过程变成 DFS），在寻找负环时可能具有更高效率，但最坏时间复杂度仍然为指数级。
LLL 优化：将普通队列换成双端队列，每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾，否则插入队首。
SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。
D´Esopo-Pape 算法：将普通队列换成双端队列，如果一个节点之前没有入队，则将其插入队尾，否则插入队首。

Dijkstra

void dijkstra(int s){
	typedef pair <int,int> node;
	priority_queue<node,vector<node>,greater<node> >q;
	for(int i =1;i<=n;i++)dis[i] = INF;
	dis[s] = 0;
	q.push(make_pair(dis[s],s));
	while(!q.empty()){
		int u = q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t;
			if(dis[v] > dis[u] + edge[i].w){
				dis[v] = dis[u] + edge[i].w;
				if(!vis[v]){
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
	return;
}

网络流

最大流

Edmonds-Karp

(慎用)

const int maxn = 10005;
const int maxm = 4e5+10;
const int INF = 1e9;
int head[maxn],parent[maxn],approve[maxn];
struct Edge{
	int from,to,next,w,cap,flow;
}edge[maxm];
int n,m,start,to,cnt,ans;//cnt = 0 so we can calculate "backedge" easily
void addedge(int from,int to,int cap,int flow){
	edge[cnt].cap = cap;
	edge[cnt].flow = flow;
	edge[cnt].to = to;
	edge[cnt].from = from;
	edge[cnt].next = head[from];
	head[from] = cnt++;
}
int BFS(int s,int t){
	queue<int>q;
	memset(approve,0,sizeof(approve)); 
	q.push(s);
	approve[s] = INF;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].to;
			if(!approve[v] and edge[i].cap > edge[i].flow){
				parent[v] = i;
				approve[v] = min(approve[u],edge[i].cap - edge[i].flow);
				q.push(v);
			}
		}
		if(approve[t])break;
	}
	return approve[t];
}
int EK(int s,int t){
	int flow = 0;
	while(1){
		int delta = BFS(s,t);
		if(!delta)break;
		for(int u = t;u != s;u = edge[parent[u]].from){
			int curp = parent[u];
			edge[curp].flow += delta;
			edge[curp^1].flow -= delta;
		}
		flow += delta;
	}
	return flow;
}

Dinic

记得加上容量为0的反向弧=-=

1 2	addedge(f,t,w,0); addedge(t,f,0,0);

struct Edge{
	int t,cap,flow,rev;
	bool is_rev;
};
vector<Edge>G[maxn];
int cur[maxn],dis[maxn],vis[maxn];
struct Dinic{
	int n;
	int flow = 0;
	void addedge(int f,int t,int cap,int flow,bool is_rev = 0){
		int rev_cnt = G[t].size();
		if(is_rev)rev_cnt--;
		G[f].push_back({t,cap,flow,rev_cnt,is_rev});
	}
	void add(int f,int t,int w){
		addedge(f,t,w,0,false);
		addedge(t,f,0,0,true);
	}
	void clear(){
		for(int i = 0;i <= n;i++){
			G[i].clear();
			G[i].shrink_to_fit();
			cur[i] = vis[i] = dis[i] = 0;
		}
		flow = 0;
		n = 0;
	}
	void init(int N){
        clear();
		n = N + 1;
	}
	bool BFS(int s,int t){
		for(int i = 0;i <= n;i++)cur[i] = 0;
		for(int i = 0;i <= n;i++)vis[i] = 0;
		queue<int>q;
		q.push(s);
		vis[s] = 1;
		dis[s] = 0;
		while(q.size()){
			int u = q.front();
			q.pop();
			for(auto it:G[u]){
				int v = it.t;
				if(!vis[v] and it.cap > it.flow){
					vis[v] = 1;
					dis[v] = dis[u] + 1;
					q.push(v);
				}
			}
		}
		return vis[t];
	}
	int DFS(int u,int T,int appr){
		if(u == T or !appr)return appr;
		int flow = 0,delta = 0;
		for(int & i = cur[u];i < (int)G[u].size();i++){
			auto it = G[u][i];
			int v = it.t;
			// cur[u] = i;
			if(dis[u] + 1 == dis[v] and (delta = DFS(v,T,min(appr,it.cap - it.flow))) > 0){
				G[u][i].flow += delta;
				G[v][it.rev].flow -= delta;
				flow += delta;
				appr -= delta;
				if(!appr)break;
			}
		}
		return flow;
	}
	
	int Maxflow(int s,int t){
		while(BFS(s,t)){
			// cout << "flow: " << flow << endl;
	 		flow += DFS(s,t,INF);
		}
		return flow;
	}
}dic;

最小费用最大流

全局变量flow为最大流,cost为最小费用

记得反向边容量为0费用为负=-=

注意使用到了全局变量n

const int maxn = 10005;
const int maxm = 4e5+10;
const int INF = 1e9;
int head[maxn],approve[maxn],dis[maxn],vis[maxn];
pair<int,int> parent[maxn];
struct Edge{
	int t,w,cap,flow,cost,rev;
	bool is_rev;
};
int n,m,start,to,cnt,ans,flow,cost;
vector<Edge>G[maxn];
void addedge(int f,int t,int cap,int flow,int cost,bool is_rev){
	int rev_cnt = G[t].size();
	if(is_rev)rev_cnt--;
	G[f].push_back({t,0,cap,flow,cost,rev_cnt,is_rev});
}
void add(int f,int t,int cap,int flow,int cost){
	addedge(f,t,cap,flow,cost,false);
	addedge(t,f,0,0,-cost,true);
}
int spfa(int s,int t){
	for(int i = 1;i <= n;i++){
		dis[i] = INF;
		vis[i] = 0;
		approve[i] = 0;
	}
	queue<int>q;
	q.push(s);
	approve[s] = INF;
	dis[s] = 0;
	vis[s] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = 0;i < G[u].size();i++){
			Edge it = G[u][i];
			int v = it.t;
			if(dis[v] > dis[u] + it.cost and it.cap > it.flow){
				parent[v] = {u,i};
				approve[v] = min(approve[u],it.cap - it.flow);
				dis[v] = dis[u] + it.cost;
				if(!vis[v]){
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return approve[t];
}
int EK(int s,int t){
//	int flow = 0;
	while(1){
		int delta = spfa(s,t);
		if(!delta)break;
		for(int u = t;u != s;u = parent[u].first){
			auto [curpx,curpy] = parent[u];
			G[curpx][curpy].flow += delta;
			int rev = G[curpx][curpy].rev;
			G[u][rev].flow -= delta;
		}
		flow += delta;
		cost += dis[t]*delta;
	}
	return flow;
}

上下界网络流

以下设源汇点为 $s_{1}, t_{1}$ , 超级源汇为 $S, T$ , 每条边的上界为 $u$ , 下界为 $l$

无源无汇上下界可行流

将原网络拆成两个图: 下界网络(每条边的容量和流量都是 $l_{i}$ , 不用实际建出) 和差网络(每条边的容量为 $u_{i} - l_{i}$ , 流量为 $0$ ).

设 $p f l o w [i]$ 为第 $i$ 个点的净流量(即流入量减流出量). 如果 $p f l o w [i] > 0$ , 在差网络上建一条 $(S, i, p f l o w [i])$ 的边来补偿 $i$ 点缺失的流出量. 如果 $p f l o w [i] < 0$ , 建一条 $(i, T, - p f l o w [i])$ 的边. 然后跑从 $S$ 到 $T$ 的最大流, 如果 $S$ 的任一出边或者 $T$ 的任一入边没有满流则不存在可行流. 否则每条边的可行流为 $f l o w_{i} + l_{i}$

int n,m;
cin >> n >> m;
int S = n+1,T = n+2;
N = T+1;
memset(head,-1,sizeof(head));
for(int i = 1;i <= m;i++){
	int f,t,l,u;
	cin >> f >> t >> l >> u;
	pflow[f] -= l,pflow[t] += l;
	lowedge[cnt] = l;
	add(f,t,u-l);
}
for(int i = 1;i <= n;i++){
	if(pflow[i] > 0)add(S,i,pflow[i]);
	else if(pflow[i] < 0)add(i,T,-pflow[i]);
}
Dinic(S,T);
bool ok = 1;
for(int i = head[S];~i;i = edge[i].next){
	if(edge[i].cap != edge[i].flow)ok = 0;
}
cout << (ok?"YES\n":"NO");
if(ok){
	for(int i = 0;i < m*2;i += 2)cout << edge[i].flow + lowedge[i] << endl;
}

有源有汇上下界可行流

在无源无汇上下界可行流的基础上, 建一条 $(t_{i}, s_{i}, \infin)$ 的边. 这条边的流量就是可行流流量

有源有汇上下界最大流

在有源有汇上下界可行流的基础上:

先跑一次 $S$ 到 $T$ 的最大流, 设 $f l o w_{1}$ = $(t_{i}, s_{i}, \infin)$ 边的流量并判断是否存在可行流. 如果存在就把这条边删掉, 再在残余网络上跑一次从 $s_{i}$ 到 $t_{i}$ 的最大流 $f l o w_{2}$ . 答案即为 $f l o w_{1} + f l o w 2$

int n,m,s1,t1;
	cin >> n >> m >> s1 >> t1;
	int S = n+1,T = n+2;
	N = T+1;
	memset(head,-1,sizeof(head));
	for(int i = 1;i <= m;i++){
		int f,t,l,u;
		cin >> f >> t >> l >> u;
		pflow[f] -= l,pflow[t] += l;
		lowedge[cnt] = l;
		add(f,t,u-l);
	}
	for(int i = 1;i <= n;i++){
		if(pflow[i] > 0)add(S,i,pflow[i]);
		else if(pflow[i] < 0)add(i,T,-pflow[i]);
	}
	add(t1,s1,INF);
	int flow = 0;
	Dinic(S,T);
	bool ok = 1;
	for(int i = head[S];~i;i = edge[i].next){
		if(edge[i].cap != edge[i].flow)ok = 0;
	}
	for(int i = head[s1];~i;i = edge[i].next){
		if(edge[i].t == t1){
			flow += abs(edge[i].flow);
			edge[i].flow = edge[i^1].flow = edge[i].cap = edge[i^1].cap = 0;
		}
	}
	flow += Dinic(s1,t1);
	if(ok){
		cout << flow;
	}
	else cout << "please go home to sleep";

有源有汇上下界最小流

同有源有汇上下界最大流, 只是在第二步时跑 $t_{i}$ 到 $s_{i}$ 的最大流, 答案为 $f l o w_{1} - f l o w_{2}$

常用模型

DAG最小覆盖问题

给定有向图 $G = (V, E)$ 且 $n = | V |$ . 设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合. 如果 $V$ 中每个定点恰好在 $P$ 的一条路上, 则称 $P$ 是 $G$ 的一个路径覆盖. $P$ 中路径可以从 $V$ 的任何一个定点开始, 长度也是任意的, 特别地, 可以为 $0$ . $G$ 的最小路径覆盖是 $G$ 所含路径条数最少的路径覆盖.

将原图的点拆为 $i$ 和 $i + n$ . 设超级源 $S$ , 超级汇 $T$ . $S$ 向点 $1. . . n$ 连边, 点 $1 + n . . . n + n$ 向 $T$ 连边, 若有 $< i, j >\in E$ 则 $i$ 向 $j + n$ 连边. 求出 $S$ 到 $T$ 的最大流 $f$ , 则 $n - f$ 为路径条数最少的路径覆盖. 方案可从流量网络中还原.

建图:

int S = 2*n+1,T = 2*n+2;
	for(int i = 1;i <= n;i++){
		add(S,i,1);
		add(i+n,T,1);
	}
	for(int i = 1;i <= m;i++){
		int f,t;
		cin >> f >> t;
		add(f,t+n,1);
	}
	N = T;
	int ans = Dinic(S,T);

求方案:

void solution(){
	static int nxt[maxn],has[maxn];
	for(int i = 1;i <= n;i++)nxt[i] = -1,has[i] = 0;
	for(int i = 0;i <= cnt;i+=2){
		int u = edge[i].f,v = edge[i].t - n;
		if(edge[i].flow == 1 and v > 1 and u <= n){
			nxt[u] = v;
			has[v] = 1;
		}
	}
	for(int i = 1;i <= n;i++)if(!has[i]){
		cout << i << " ";
		int u = nxt[i];
		while(u != -1){
			cout << u << " ";
			u = nxt[u];
		}
		cout << endl;
	}
}

二分图匹配

常识性知识

所有的树是二分图
所有的网格图和四边形图是二分图
设 $u, v$ 为两个 $k$ 进制数且 $u, v$ 只有一位不同且该位差值为1. 若图中的所有边的两个顶点 $u_{i}, v_{i}$ 均满足该性质, 则该图是二分图(将每一位加起来后的值按奇偶分类)
最大匹配数：最大匹配的匹配边的数目

最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择

最大独立数：选取最多的点，使任意所选两点均不相连

最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

定理1：最大匹配数 = 最小点覆盖数（Konig 定理）

定理2：最大匹配数 = 最大独立数

定理3：最小路径覆盖数 = 顶点数 - 最大匹配数

二分图最大匹配

网络流做法

建立超级源 $S$ 和超级汇 $T$ , 从 $S$ 向每个左端点连边, 每个右端点向 $T$ 连边, 端点之间按给出的图连边(仅从左端点向右端点), 边权均为1.

$S$ 到 $T$ 的最大流就是最大匹配

用Dinic实现复杂度 $O (\sqrt{n} m)$

KM

复杂度 $O (n m)$

match[v]为 $v$ 的匹配点.

a为左端点点的个数, b为右端点点的个数

bool KM(int u){
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v])continue;
		vis[v] = 1;
		if(!match[v] or KM(match[v])){
			match[v] = u;
			match[u] = v;
			return 1;
		}
	}
	return 0;
}
int match_cnt = 0;
for(int i = 1;i <= a;i++){
    for(int j = 0;j <= a+b;j++)vis[j] = 0;
    match_cnt += KM(i);
}
cout << match_cnt;

二分图最大带权匹配

复杂度 $O (n^{3})$ . 使用addEdge(f,t,w)加边. 注意下标从0开始. 有空改成自己的板子

template <typename T>
struct hungarian {  // km
  int n;
  vector<int> matchx;  // 左集合对应的匹配点
  vector<int> matchy;  // 右集合对应的匹配点
  vector<int> pre;     // 连接右集合的左点
  vector<bool> visx;   // 拜访数组 左
  vector<bool> visy;   // 拜访数组 右
  vector<T> lx;
  vector<T> ly;
  vector<vector<T> > g;
  vector<T> slack;
  T inf;
  T res;
  queue<int> q;
  int org_n;
  int org_m;

  hungarian(int _n, int _m) {
    org_n = _n;
    org_m = _m;
    n = max(_n, _m);
    inf = numeric_limits<T>::max();
    res = 0;
    g = vector<vector<T> >(n, vector<T>(n));
    matchx = vector<int>(n, -1);
    matchy = vector<int>(n, -1);
    pre = vector<int>(n);
    visx = vector<bool>(n);
    visy = vector<bool>(n);
    lx = vector<T>(n, -inf);
    ly = vector<T>(n);
    slack = vector<T>(n);
  }

  void addEdge(int u, int v, int w) {
    g[u][v] = max(w, 0);  // 负值还不如不匹配 因此设为0不影响
  }

  bool check(int v) {
    visy[v] = true;
    if (matchy[v] != -1) {
      q.push(matchy[v]);
      visx[matchy[v]] = true;  // in S
      return false;
    }
    // 找到新的未匹配点 更新匹配点 pre 数组记录着"非匹配边"上与之相连的点
    while (v != -1) {
      matchy[v] = pre[v];
      swap(v, matchx[pre[v]]);
    }
    return true;
  }

  void bfs(int i) {
    while (!q.empty()) {
      q.pop();
    }
    q.push(i);
    visx[i] = true;
    while (true) {
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
          if (!visy[v]) {
            T delta = lx[u] + ly[v] - g[u][v];
            if (slack[v] >= delta) {
              pre[v] = u;
              if (delta) {
                slack[v] = delta;
              } else if (check(v)) {  // delta=0 代表有机会加入相等子图 找增广路
                                      // 找到就return 重建交错树
                return;
              }
            }
          }
        }
      }
      // 没有增广路 修改顶标
      T a = inf;
      for (int j = 0; j < n; j++) {
        if (!visy[j]) {
          a = min(a, slack[j]);
        }
      }
      for (int j = 0; j < n; j++) {
        if (visx[j]) {  // S
          lx[j] -= a;
        }
        if (visy[j]) {  // T
          ly[j] += a;
        } else {  // T'
          slack[j] -= a;
        }
      }
      for (int j = 0; j < n; j++) {
        if (!visy[j] && slack[j] == 0 && check(j)) {
          return;
        }
      }
    }
  }

  void solve() {
    // 初始顶标
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        lx[i] = max(lx[i], g[i][j]);
      }
    }

    for (int i = 0; i < n; i++) {
      fill(slack.begin(), slack.end(), inf);
      fill(visx.begin(), visx.end(), false);
      fill(visy.begin(), visy.end(), false);
      bfs(i);
    }

    // custom
    for (int i = 0; i < n; i++) {
      if (g[i][matchx[i]] > 0) {
        res += g[i][matchx[i]];
      } else {
        matchx[i] = -1;
      }
    }
    cout << res << "\n";
    for (int i = 0; i < org_n; i++) {
      cout << matchx[i] + 1 << " ";
    }
    cout << "\n";
  }
};

应用

二分图最大点独立集

个数为顶点数-最大匹配数

二分图最小点覆盖(König 定理)

最小点覆盖: 选择最小的点集 $S$ 使得任意一条边至少有一个顶点在 $S$ 里. 二分图的最小点覆盖数 = 最大匹配数.

构造方案: 从左边的未匹配点开始dfs, 从左向右走未匹配边, 从右向左走匹配边(类似KM), 将经过的点全部标记. 左边的未标记点和右边的标记点就是 $S$ .

match[v] = u表示 $u, v$ 是一条匹配边. mvis[]代表该过程标记的点. (在用Dinic求二分图时需要去掉源点汇点S,T)

int match[maxn],mvis[maxn];
void MVC(int u,int S,int T,bool flag){
	if(u == S or u == T)return;
	mvis[u] = 1;
	if(flag){
		if(!mvis[match[u]])MVC(match[u],S,T,!flag);
	}
	else{
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].to;
			if(mvis[v])continue;
			MVC(v,S,T,!flag);
		}
	}
}

mvc即为所求点集:

for(int i = 1;i <= n1;i++)if(!match[i]){
		MVC(i,S,T,0);
}
vector<int>mvc;
for(int i = 1;i <= n1;i++)if(!mvis[i])mvc.push_back(i);
for(int i = n1+1;i <= n1+n2;i++)if(mvis[i])mvc.push_back(i);

二分图博弈

考虑如下问题: 有两名玩家 $A$ 和 $B$ , 轮流进行游戏且 $A$ 先手. 玩家每次可从当前状态转移到相邻的状态, 且已经访问过的状态不能再次访问. 状态可分为两个不相交的集合(建成二分图). 不能操作的玩家输.

概念:

完美匹配: 图中所有点均属于最大匹配
必经点: 任意一个最大匹配均包含的点
非必经点: 至少一个最大匹配不包含的点.

结论: 如果状态图最大匹配是完美匹配, 则 $A$ 必败. 否则, 如果游戏从非必经点开始, $A$ 必胜. 其他情况 $A$ 必败.

简要推导: 如果 $A$ 从必经点开始, 那么 $B$ 总存在一种策略让自己走非匹配边, 使得 $A$ 必须走上匹配边, 最后 $A$ 将无路可走. 而如果 $A$ 从非必经点开始, 则 $A$ 一定会走到一个必经点, 转换为 $B$ 从必经点开始.

至此问题转化为求二分图中的所有非必经点.

方法一: KM

时间复杂度 $O (n m)$ , 适用于比较小的图.

全局变量: bool unne[]. $u n n e [i] = 1$ 表示 $i$ 为非必经点.

需要先跑一遍KM, 再对每个点 $i$ 跑unness(i). 注意特判度为0的点

bool unne[maxn];
void unness(int u){
	if(unne[u])return;
	unne[u] = 1;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(match[v])unness(match[v]);
	}
}

方法2:网络流

这里用Dinic跑. 建图约定: 和超级源相连的点颜色标为 $1$ , 和超级汇相连的点颜色标为 $0$ . 从 $S$ 出发走非满流边能到达的和 $S$ 相邻的点, 以及从 $T$ 出发走满流边能到达的和 $T$ 相邻的点均为非必经点. 复杂度 $O (\sqrt{n} m)$

使用时调用cal_unne(S,1)和cal_unne(T,0).

bool unne[maxn];
void cal_unne(int u,int c){
	if(col[u] == c)unne[u] = 1;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(edge[i].cap - edge[i].flow == c and !unne[v])cal_unne(v,c);
	}
}

方法3: 判断单个点

假设判断点 $s$ . 先建出整个图, 但不连接 $S - s$ , $s - T$ . 跑一遍网络流. 再将 $S - s, s - T$ 连接, 在残量网络里继续跑网络流. 如果流量增加那么 $s$ 是非必经点.

连通性与环

割点

void Tarjan(int u,int fa){
	if(dfn[u])return;
	dfn[u] = low[u] = dfsclock++;
	int child = 0;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].to;
		if(!dfn[v]){
			Tarjan(v,fa);
			low[u] = min(low[v],low[u]);
			if(u == fa)child++;
			if(low[v] >= dfn[u] and u != fa)iscut[u] = 1;
		}
		low[u] = min(low[u],dfn[v]);
	}
	if(fa == u and child > 1)iscut[u] = 1;
	return;
}

SCC/强连通分量

Kosaraju

G为原图，GT为反图，GD为缩点后的DAG

vector<int>G[maxn],GT[maxn],GD[maxn],GDR[maxn];
int sccno[maxn],siz[maxn];
bool vis[maxn];
int out[maxn];
int scccnt;
map<pair<int,int>,bool>dup;
vector<int>r_topo;
void add(int f,int t){
	G[f].push_back(t);
	GT[t].push_back(f);
}
void addDAG(int f,int t){
	GD[f].push_back(t);
	GDR[t].push_back(f);
	out[f]++;
}
 void DFS1(int u){
	if(vis[u])return;
	vis[u] = 1;
	for(int v:G[u])DFS1(v);
	r_topo.push_back(u);
	return;
}
void DFS2(int u){
	if(sccno[u])return;
	sccno[u] = scccnt;
	siz[scccnt]++;
	for(int v:GT[u])DFS2(v);
	return;
}
void findscc(int n){
	for(int i = 1;i <= n;i++)DFS1(i);
	for(int i = n-1;i >= 0;i--){
		if(!sccno[r_topo[i]]){
			scccnt++;
			DFS2(r_topo[i]);
		}
	}
}
void buildmap(int n){
	for(int u = 1;u <= n;u++){
		for(int v:G[u]){
			if(sccno[u] != sccno[v]){
				// not nessseary
				// if(!dup[{sccno[u],sccno[v]}]){
				// 	dup[{sccno[u],sccno[v]}] = 1;
				// }
				addDAG(sccno[u],sccno[v]);
			}
		}
	}
}

桥

一种比较好理解的求桥的方法 (注意无法用来求割顶

$d p [u]$ 表示跨过 $u$ 的反向边的数量.如果 $d p [u] == 0$ 则 $< f a, u >$ 为桥( $f a$ 是 $u$ 的父亲)

调用时需初始化 $d e p [r o o t] = 1$

void Cal_bri(int u,int fa){
	dp[u] = 0;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(v == fa)continue;
		if(!dep[v]){
			dep[v] = dep[u]+1;
			Cal_bri(v,u);
			dp[u] += dp[v];
		}
		else{
			if(dep[v] > dep[u])dp[u]--;
			else if(dep[v] < dep[u]){
				dp[u]++;
			}
		}
	}
	if(!dp[u] and dep[u] > 1)ok = 0;
}

仙人掌

(接上文)点仙人掌中求环并缩点

$b a c k c n t$ 为全局变量,初始化为 $n + 1$ (点的个数+1)

$p h a s h [u]$ 返回环的标号,从 $n + 1$ 开始.若不在环内则 $p h a s h [u] == u$

调用时初始化 $d e p [r o o t] = 1$ ,注意缩点后需要重新寻找根节点(缩点代码未给出)

原理参见https://codeforces.com/blog/entry/68138 这个东西应该找简单环都可以用(?

void Cal_bri(int u,int fa){
	dp[u] = 0;
	bool ok = 0;
	for(int i = rhead[u];~i;i = redge[i].next){
		int v = redge[i].to;
		if(v == fa)continue;
		if(!dep[v]){
			dep[v] = dep[u]+1;
			Cal_bri(v,u);
			dp[u] += dp[v];
		}
		else{
			if(dep[v] > dep[u])dp[u]--;
			else if(dep[v] < dep[u]){
				in[v]++;
				dp[u]++;
				ok = 1;
				redge[i].cnt = ++backcnt;
			}
		}
	}
	if(ok)phash[u] = backcnt;
	else{
		phash[u] = u;
		for(int i = rhead[u];~i;i = redge[i].next){
			int v = redge[i].to;
			if(v == fa)continue;
			if(phash[v] != v and !in[v]){
				phash[u] = phash[v];
			}
		}
	}
}

BFS求最小环

见代码=-=可以画个BFS树或者手模感悟一下

记得得枚举1...n的所有起点,所以复杂度是 $O (n^{2})$

void BFS(int s){
	memset(dis,-1,sizeof(dis));
	dis[s] = 0;
	queue<pair<int,int> >q;
	q.push(make_pair(s,0));
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		int u = now.first,fa = now.second;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t;
			if(v == fa)continue;
			if(dis[v] == -1){
				dis[v] = dis[u]+1;
				q.push(make_pair(v,u));
			}
			else{
				ans = min(ans,dis[v]+dis[u]+1);
			}
		}
	}
}

Floyd求最小环

int val[maxn + 1][maxn + 1];  // 原图的邻接矩阵
inline int floyd(const int &n) {
  static int dis[maxn + 1][maxn + 1];  // 最短路矩阵
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) dis[i][j] = val[i][j];  // 初始化最短路矩阵
  int ans = inf;
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        ans = std::min(ans, dis[i][j] + val[i][k] + val[k][j]);  // 更新答案
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        dis[i][j] = std::min(
            dis[i][j], dis[i][k] + dis[k][j]);  // 正常的 floyd 更新最短路矩阵
  }
  return ans;
}

2-SAT

参数a,x,b,y代表 $x_{a}$ 为x或 $x_{b}$ 为y x,y是bool 是的我知道这个变量起的很弱智

//P4782
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
const int maxm = 4E6+10;
struct Edge{
	int from,to,next;
}edge[maxm],edgeT[maxm];
vector<int>r_topo;
int scc_no[maxn],scc_cnt;
bool vis[maxn];
int cnt = 1,cntT = 1,head[maxn],headT[maxn],n,m,q;
void addedge(int f,int t){
	edge[cnt].from = f;
	edge[cnt].to = t;
	edge[cnt].next = head[f];
	head[f] = cnt++;
	edgeT[cntT].from = t;
	edgeT[cntT].to = f;
	edgeT[cntT].next = headT[t];
	headT[t] = cntT++;
}
void DFS1(int u){
	if(vis[u])return;
	vis[u] = 1;
	for(int i = head[u];~i;i = edge[i].next){
		DFS1(edge[i].to);
	}
	r_topo.push_back(u);
}
void DFS2(int u){
	if(scc_no[u])return;
	scc_no[u] = scc_cnt;
	for(int i = headT[u];~i;i = edgeT[i].next)DFS2(edgeT[i].to);
}
void findscc(){
	for(int i = 1;i <= 2*n;i++)DFS1(i);
	for(int i = 2*n-1;i >= 0;i--){
		if(!scc_no[r_topo[i]]){
			scc_cnt++;
			DFS2(r_topo[i]);
		}
	}
}
int main(){
//	freopen("P4782.in","r",stdin);
	memset(head,-1,sizeof(head));
	memset(headT,-1,sizeof(headT));
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		int a,b,x,y;
		scanf("%d%d%d%d",&a,&x,&b,&y);
		addedge(a+n*(x&1),b+n*(y^1));
		addedge(b+n*(y&1),a+n*(x^1));
	}
	findscc();
	bool ok = 1;
	for(int i = 1;i <= n;i++)if(scc_no[i] == scc_no[i+n]){
		ok = 0;
		break;
	}
	if(!ok)printf("IMPOSSIBLE");
	else{
		printf("POSSIBLE\n");
		for(int i = 1;i <= n;i++)printf("%d ",scc_no[i] > scc_no[i+n]);
	}
	return 0;
}

弦图

定义

子图: 点集和边集均为原图点集和边集子集的图.

导出子图: 点集为原图点集的子集, 且边集中所有边的两个端点都在导出子图的点集中.

团: 是完全图的子图

单纯点: 设 $N (x)$ 为所有与 $x$ 相邻的点的集合, 若 ${x} + N (x)$ 的导出子图是团, 则 $x$ 是单纯点

完美消除序列

此处完美消除序列(Perfect Elimination Ordering)的定义为: 令 $n = | V |$ ，完美消除序列 $v_{1}, v_{2}, \dots, v_{n}$ 为 $1, 2, \dots, n$ 的一个排列，满足 $v_{i}$ 在 ${v_{i}, v_{i + 1}, \dots, v_{n}}$ 的导出子图中为单纯点.

注意该定义可能与部分论文顺序相反.

最大势算法(MCS)

优先队列做法

已弃用, 有可能RE

复杂度: $O ((n + m) \log n)$

输入: $n$ , 点数

$h e a d [], e d g e [], c n t$ , 无向图(全局变量)

使用的全局变量: $v i s []$

输出: vector<int>, 长度为 $n$ 的完美消除序列.

vector<int> MCS(int n){
	vector<int>res;
	priority_queue<pair<int,int> >pq;
	for(int i = 1;i <= n;i++){
		label[i] = vis[i] = 0;
		pq.push({0,i});
	}
	for(int step = 1;step <= n;step++){
		while(pq.size()){
			int u = pq.top().second;
			pq.pop();
			if(!vis[u]){
				res.push_back(u);
				vis[u] = 1;
				for(int i = head[u];~i;i = edge[i].next){
					int v = edge[i].t;
					if(vis[v])continue;
					label[v]++;
					pq.push({label[v],v});
				}
				break;
			}
		}
	}
	reverse(res.begin(),res.end());
	return res;
}

链表做法

复杂度 $O (n + m)$

vector<int> MCS(int n){
	int best = 0;
	vector<int>res;
	vector<list<int> >link(n+1);
	for(int i = 1;i <= n;i++){
		label[i] = vis[i] = 0;
		link[0].push_back(i);
	}
	for(int step = 1;step <= n;step++){
		while(best >= 0){
			if(!link[best].size()){
				best--;
				continue;
			}
			int u = link[best].front();
			link[best].pop_front();
			if(!vis[u]){
				vis[u] = 1;
				res.push_back(u);
				for(int i = head[u];~i;i = edge[i].next){
					int v = edge[i].t;
					if(!vis[v]){
						label[v]++;
						link[label[v]].push_back(v);
						if(label[v] > best)best = label[v];
					}
				}
			}
		}
	}
	reverse(res.begin(),res.end());
	return res;
}

判断完美消除序列是否合法

根据完美消除序列的定义，设 $v_{i}$ 在 $v_{i}, v_{i + 1}, \dots, v_{n}$ 中相邻的点从小到大为 ${v_{c_{1}}, v_{c_{2}}, \dots, v_{c_{k}}}$ ，则只需判断 $v_{c_{1}}$ 与其他点是否直接连通即可

输入:int n-图的点数 vector<int> & peo-完美消除序列

输出: 该序列是否合法

时间复杂度 $O (m \log n + n)$

bool chord_check(int n,vector<int> & peo){
	static bool mark[maxn];
	static int rank[maxn];
	for(int i = 0;i < n;i++)rank[peo[i]] = i,mark[i] = 0;
	for(int u:peo){
		vector<pair<int,int> >tmp;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t;
			if(!mark[v])tmp.push_back({rank[v],v});
		}
		sort(tmp.begin(),tmp.end());
		if(tmp.size()){
			int u = tmp[0].second;
			set<int>tmpadj;
			for(int i = head[u];~i;i = edge[i].next){
				int v = edge[i].t;
				tmpadj.insert(v);
			}
			for(int i = 1;i < (int)tmp.size();i++){
				if(!tmpadj.count(tmp[i].second))return 0;
			}
		}
		mark[u] = 1;
	}
	return 1;
}

弦图最大独立集/最小团覆盖

最大独立集: 从前往后遍历完美消除序列, 每次选取不在独立集且与独立集无邻边的点加入独立集中.

最小团覆盖: 设最大独立集为 ${v_{1}, v_{2}, \dots, v_{t}}$ , 则团的集合 ${$ ${v_{1} + N (v_{1})}, {v_{2} + N (v_{2})}, . . ., {v_{t} + N (v_{t})}$ $}$ 为图的最小团覆盖. 时间复杂度均为 $O (n + m)$

弦图的色数/弦图的团数

一种构造方法：按完美消除序列从后往前依次给每个点染色，给每个点染上可以染的最小颜色。时间复杂度 $O (m + n)$ 。

正确性证明：设以上方法使用了 $t$ 种颜色，则 $t \geq χ (G)$ 。由于团上每个点都是不同的颜色，所以 $t = ω (G)$ ，由 Lemma 1， $t = ω (G) \leq χ (G)$ 。综上，可得 $t = χ (G) = ω (G)$ 。

无需染色方案，只需求出弦图的色数/团数时，可以取 $| {x} + N (x) |$ 的最大值得到。

树

最小生成树

结论

同一个图的任意最小生成树上, 每种权值的边的数量是固定的.
切分定理：对于给定图的任意割，横跨两个割集的边中权值严格最小的边必定在最小生成树上
假设权值为 $w$ 的边需要 $k$ 条来形成最小生成树且已经加入 $k$ 条, 那么无论选择了哪些合法的边, 图的联通状态都是相同的

Prim

$d i s [i]$ 表示第 $i$ 条树边的长度,标号从 $2$ 到 $n$ .

$d [i] [j]$ 为边 $< i, j >$ 权值

int prim(int n){
	for(int i = 0;i <= n;i++)vis[i] = 0,dis[i] = INF;
	for(int i = 1;i < n;i++){
		int x = 0;
		for(int j = 1;j <= n;j++)if(!vis[j]){
			if(!x or dis[x] > dis[j])x = j;
		}
		vis[x] = 1;
		for(int j = 1;j <= n;j++)if(!vis[j]){
			dis[j] = min(dis[j],d[x][j]);
		}
	}

	ll tans = 0;
	for(int i = 2;i <= n;i++){
		tans += dis[i];
	}
	return tans;
}

欧拉序

定义

在dfs整个树的过程中, 第一次访问或回溯时均记录下经过的节点即为欧拉序. 例:

这棵树的欧拉序(根节点为1)为1 2 3 4 3 7 3 2 5 6 5 2 1

一棵 $n$ 个节点的树欧拉序长度为 $2 n - 1$ . ( $n$ 个点, $n - 1$ 条边)

int clk;//下标指针
int euler[maxn],dep[maxn],fir[maxn],lst[maxn];//欧拉序, 深度, 节点第一次(最后一次)在欧拉序中出现的位置
void dfs(int u,int fa){
	euler[++clk] = u;
	fir[u] = lst[u] = clk;
	dep[u] = dep[fa] + 1;
	for(int v:G[u]){
		if(v != fa){
			dfs(v,u);
			euler[++clk] = u;
            lst[u] = clk;
		}
	}
}

将树上问题转化为区间问题

欧拉序可将一棵树映射为一维的区间. $[f i r [u], l s t [u]]$ 之间的欧拉序对应的是以 $u$ 为根的子树的区间.

求解LCA

$O (n \log n)$ 预处理, $O (1)$ 查询. $u, v$ 之间的LCA即为欧拉序 $[f i r [u], f i r [v]]$ 之间深度最小的点.

ST表中保存的是点的编号, 但按点的深度来比较.

void ST_init(int n){
	lg[0] = -1;
	for(int i = 1;i <= n;i++)ST[i][0] = euler[i];
	for(int i = 1;i < maxn;i++)lg[i] = lg[i>>1] + 1;
	for(int j = 1;(1<<j) <= n;j++)
		for(int i = 1;i +(1<<j) - 1<= n;i++){
		int v1 = ST[i][j - 1],v2 = ST[i + (1<<(j - 1))][j - 1];
		ST[i][j] = dep[v1] < dep[v2]?v1:v2;
	}
}
int query(int u,int v){
	if(fir[u] > fir[v])swap(u,v);
	u = fir[u],v = fir[v];
	int k = lg[v-u+1];
	int v1 = ST[u][k],v2 = ST[v - (1<<k) + 1][k];
	return dep[v1] < dep[v2]?v1:v2;
}

DFS序

上图的DFS序(不唯一)为1 2 3 4 4 7 7 3 5 6 6 5 2 1

一棵大小为 $n$ 的树DFS序长度为 $2 n$ .

最近公共祖先(LCA)-倍增

预处理 $O (n)$ , 单次查询 $O (\log)$

void pre(int u,int fa){
	if(u == fa)return;
	dep[u] = dep[fa] + 1;
	pa[u][0] = fa;
	for(int i = 1;(1<<i) <= dep[u];i++)pa[u][i] = pa[pa[u][i-1]][i-1];
	for(auto [v,w]:G[u])if(fa != v)pre(v,u);
}
int LCA(int a,int b){
	if(dep[a] > dep[b])swap(a,b);
	for(int i = 30;i >= 0;i--){
		if(dep[a] <= dep[b] - (1<<i))b = pa[b][i];
	}
	if(a == b)return a;
	for(int i = 30;i >= 0;i--){
		if(pa[a][i] == pa[b][i])continue;
		else{
			a = pa[a][i];b = pa[b][i];
		}
	}
	return pa[a][0];
}

重心

$w [u]$ 为删去 $u$ 后剩余连通分量的最大值, $r t$ 为树的重心

树最多有两个相邻的重心

void cent(int u,int fa){
	siz[u] = 1;
	w[u] = 0;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].to;
		if(v != fa){
			cent(v,u);
			siz[u] += siz[v];
			w[u] = max(w[u],siz[v]);
		}
	}
	w[u] = max(w[u],n - siz[u]);
	if(!rt or w[u] < w[rt])rt = u;
}

最大独立集

树也是二分图, 最大独立集可以在多项式时间内求.

例题: 求最大带权独立集.

写法1

w[]是点权, ans[u]代表以 $u$ 为根的子树最大带权独立集权值和, fa和gr分别代表 $u$ 的父亲和祖父. f[u][0]为 $u$ 所有儿子节点ans的和, f[u][1]为 $u$ 所有孙子节点ans的和.

void dfs(int u,int fa,int gr){
	for(int v:G[u])if(v != fa){
		dfs(v,u,fa);
	}
	ans[u] = max(f[u][0],f[u][1] + w[u]);
	f[fa][0] += ans[u];
	f[gr][1] += ans[u];
}

写法2(方便扩展和还原方案)

f[u][0]表示 $u$ 不在独立集里的最优答案, f[u][1]表示 $u$ 在独立集里的最优答案.

int dfs(int u,int fa,int c){
	if(f[u][c] != -1)return f[u][c];
	int x = (c?w[u]:0);
	for(int v:G[u])if(v != fa){
		int r = dfs(v,u,0);
		if(!c)r = max(r,dfs(v,u,1));
		x += r;
	}
	return f[u][c] = x;
}

DMST/最小树形图/有向图最小生成树

Edmond's Algorithm. 代码来自HDU6990的官方题解.

输入: es[] = edge(起点, 终点, 权值)

调用solve(顶点数, 边数)

输出: ans[], ans[i]代表以 $i$ 为根的DMST权值(即 $i$ 到其它点都有一条路径可达), 若不存在则为 $- 1$

时间复杂度 $O (m l o g n)$

struct DMST{
    const ll inf = 4e13;
    struct edge { int u, v; ll w; } es[maxn];
    int ls[maxn], rs[maxn], dis[maxn];
    ll val[maxn], tag[maxn];
    void update(int x, ll t) { val[x] += t;tag[x] += t; }
    void push_down(int x) {
        if (ls[x]) update(ls[x], tag[x]);
        if (rs[x]) update(rs[x], tag[x]);
        tag[x] = 0;
    }

    int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (val[x] > val[y]) swap(x, y);
        push_down(x);
        rs[x] = merge(rs[x], y);
        if (dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]);
        dis[x] = dis[rs[x]] + 1;
        return x;
    }
    int top[maxn], fa[maxn], ine[maxn];
    int findset[maxn]; int find(int x) { return findset[x] ? findset[x] = find(findset[x]) : x; }
    vector<int> ch[maxn];

    ll ans[maxn];
    void dfs(int u, ll s) {
        if (ch[u].empty())
            ans[u] = s >= inf ? -1 : s;
        else for (int v : ch[u])
            dfs(v, s - val[ine[v]]);
    }

    void solve(int n, int m) {
        for (int i = 1; i <= 2 * n; ++i) top[i] = fa[i] = ine[i] = findset[i] = 0, ch[i].clear();
        for (int i = 1; i <= n; ++i) es[++m] = { i % n + 1, i, inf };
        for (int i = 1; i <= m; ++i) {
            ls[i] = rs[i] = tag[i] = dis[i] = 0;
            val[i] = es[i].w;
            top[es[i].v] = merge(top[es[i].v], i);
        }
        int x = 1;
        while (top[x]) {
            int i = top[x], y = find(es[i].u);
            top[x] = merge(ls[i], rs[i]);
            if (y == x) continue;
            ine[x] = i;
            if (!ine[es[i].u]) x = y;
            else for (int z = ++n; x != z; x = find(es[ine[x]].u)) {
                fa[x] = findset[find(x)] = z;
                ch[z].push_back(x);
                if (top[x]) update(top[x], -val[ine[x]]);
                top[z] = merge(top[z], top[x]);
            }
        }
        
        ll sum = 0;
        for (int i = 1; i <= n; ++i)
            sum += val[ine[i]];
        dfs(n, sum);
    }
}dmst;

树同构

AHU算法

用于解决有根树同构问题, 可以将每个子树映射到一个编号, 编号(hsh[])相等则同构. 是一个确定性算法. 下面的实现是 $O (n \log n)$ 的但可优化至 $O (n)$ . 使用时, 将两棵树存在同一个图中.

对于无根树A, B, 求出重心后分情况讨论:

重心数量不同, 不同构.
均只有一个重心, 以重心为根求解, 编号相同则同构.
均只有两个重心, 若树 $A$ 以重心1为根的编号, 和树 $B$ 以重心1或重心2为根的编号相同, 则同构.

求解编号时, 预处理出树的深度. 按深度由大到小一层层计算. 每个节点的编号信息为其所有叶子节点的编号排序之后的数组. 将该数组映射便得到该节点的编号.

下面的实现默认两个子树大小相等, 且树B的节点为原节点 $+ n$ .

#define ALL(x) (x).begin(),(x).end()
int hsh[maxn],dep[maxn];
map<vector<int>,int> id;
vector<int>rd[maxn];
int cid;
void cal_dep(int u,int fa){
	dep[u] = (fa == -1?1:dep[fa] + 1);
	for(int v:G[u])if(v != fa)cal_dep(v,u);
}
in
void cal(int r1,int r2){
	cid = 0;id.clear();
	for(int i = 1;i <= n*2;i++)dep[i] = 0;
	cal_dep(r1,-1);
	cal_dep(r2,-1);
	for(int i = 1;i <= n*2;i++)rd[i].clear(),hsh[i] = 0;
	for(int i = 1;i <= n*2;i++)rd[dep[i]].push_back(i);
	for(int i = n;i >= 1;i--){
		for(int u:rd[i]){
			vector<int>tmp;
			for(int v:G[u])tmp.push_back(hsh[v]);
			sort(ALL(tmp));
			int x = 0;
			if(id.count(tmp))x = id[tmp];
			else x = id[tmp] = ++cid;
			hsh[u] = x;
		}
	}
}

也可以用递归写法:

int hsh[maxn];
map<vector<int>,int> id;
int cid;
int dfs(int u,int fa){
	vector<int>cur;
	for(int v:G[u])if(v != fa){
		dfs(v,u);
		cur.push_back(hsh[v]);
	}
	sort(ALL(cur));
	int & tid = id[cur];
	if(!tid)tid = ++cid;
	hsh[u] = tid;
	return tid;
}

判断无根树是否同构:

int __;
cin >> __;
while(__--){
	cin >> n;
	cid = 0;
	id.clear();
	for(int i = 0;i <= n*2;i++)siz[i] = w[i] = hsh[i] = 0,G[i].clear();
	for(int i = 1;i < n;i++){
		int f,t;
		cin >> f >> t;
		G[f].push_back(t);
		G[t].push_back(f);
	}
	for(int i = 1;i < n;i++){
		int f,t;
		cin >> f >> t;
		f += n,t += n;
		G[f].push_back(t);
		G[t].push_back(f);
	}
	int rt1 = 0,rt2 = 0;
	cent(1,0,rt1);
	cent(n+1,0,rt2);
	int xrt1 = -1,xrt2 = -1;
	for(int v:G[rt1])if(w[v] == w[rt1])xrt1 = v;
	for(int v:G[rt2])if(w[v] == w[rt2])xrt2 = v;
	dfs(rt1,-1);
	dfs(rt2,-1);
	bool ok = 1;
	if((xrt1 == -1 and xrt2 != -1) or (xrt2 == -1 and xrt1 != -1))ok = 0;
	else{
		if(xrt1 == -1){
			if(hsh[rt1] != hsh[rt2])ok = 0;
		}
		else{
			if(hsh[rt1] != hsh[rt2]){
				for(int i = 1;i <= n*2;i++)hsh[i] = 0;
				cid = 0;id.clear();
				dfs(rt1,-1);
				dfs(xrt2,-1);
				if(hsh[rt1] != hsh[xrt2])ok = 0;
			}
		}
	}
	cout << (ok?"YES\n":"NO\n");
}

点分治

具体看lyd的书.这里只放几道例题

例题1-Tree

求树上间距小于等于 $k$ 的点对个数

//P4178
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn = 4e4+10;
const int maxm = 4e5+10;
int head[maxn],vis[maxn],cnt;
int dis[maxn],bal[maxn],siz[maxn];//权值,平衡因子,子树大小
int mapp[maxn],par[maxn],occur[maxn],tot;//树上点的映射,该点属于根的哪颗子树,出现次数,待处理的总数
int root,n,k,ans;
struct Edge{
	int f,t,w,next;
	Edge(int f = 0,int t = 0,int w = 0,int next = 0):f(f),t(t),w(w),next(next){}
}edge[maxm];
void addedge(int f,int t,int w){
	edge[cnt] = Edge(f,t,w,head[f]);
	head[f] = cnt++;
}
bool cmp(int a,int b){
	return dis[a] < dis[b];
}
void get_root(int u,int fa,int rawsiz){
	siz[u] = 1,bal[u] = 0;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v] or v == fa)continue;
		get_root(v,u,rawsiz);
		siz[u] += siz[v];
		bal[u] = max(bal[u],siz[v]);
	}
	bal[u] = max(bal[u],rawsiz - siz[u]);
	if(!root or bal[root] > bal[u])root = u;
}
void get_dis(int u,int fa,int w,int parent){
	mapp[++tot] = u;
	dis[u] = w,par[u] = parent;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v] or v == fa)continue;
		get_dis(v,u,w + edge[i].w,parent);
	}
}
void Cal(int u){
	tot = 0;
	mapp[++tot] = u;
	dis[u] = 0,par[u] = u;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v])continue;
		get_dis(v,u,edge[i].w,v);
	}
	sort(mapp+1,mapp+tot+1,cmp);
	// cout << tot << endl;
	int l = 1,r = tot;
	for(int i = 1;i <= tot;i++)occur[par[mapp[i]]]++;
	while(l <= r){
		if(dis[mapp[l]] + dis[mapp[r]] > k)occur[par[mapp[r--]]]--;
		else{
			ans += (r - l + 1 - occur[par[mapp[l]]]);
			occur[par[mapp[l++]]]--;
		}
	}
}
void Divide(int u){
	vis[u] = 1;
	dis[u] = 0;
	Cal(u);
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v])continue;
		root = 0;
		get_root(v,-1,siz[v]);
		Divide(root);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(head,-1,sizeof(head));
	cin >> n;
	for(int i = 1;i < n;i++){
		int f,t,w;
		cin >> f >> t >> w;
		addedge(f,t,w);
		addedge(t,f,w);
	}
	cin >> k;
	get_root(1,-1,n);
	Divide(root);
	cout << ans;
	return 0;
}

例题2-[IOI2011]Race

给出一棵树,求路径和为k的最短路径长度(边数)

//P4149
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
const int maxn = 2e6+10;
const int maxm = maxn*2;
const int INF = 1E9;
int head[maxn],vis[maxn],dis[maxn],dep[maxn];
int bal[maxn],siz[maxn],par[maxn];
int mapp[maxn],mindis[maxn];
int cnt,ans,root,n,k,tot;
struct Edge{
	int f,t,w,next;
	Edge(int f = 0,int t = 0,int w = 0,int next = 0):f(f),t(t),w(w),next(next){}
}edge[maxm];
void addedge(int f,int t,int w){
	edge[cnt] = Edge(f,t,w,head[f]);
	head[f] = cnt++;
}
bool cmp(int a,int b){
	return dis[a] < dis[b];
}
void get_root(int u,int fa,int rawsiz){
	siz[u] = 1,bal[u] = 0;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v] or v == fa)continue;
		get_root(v,u,rawsiz);
		siz[u] += siz[v];
		bal[u] = max(bal[u],siz[v]);
	}
	bal[u] = max(bal[u],rawsiz - siz[u]);
	if(!root or bal[root] > bal[u])root = u;
}
void get_dis(int u,int fa,int parent){
	par[u] = parent;
	mapp[++tot] = u;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v] or fa == v)continue;
		dis[v] = dis[u] + edge[i].w;
		dep[v] = dep[u] + 1;
		get_dis(v,u,parent);
	}
}
void Cal(int u){
	tot = 0;
	int pretot = 0;
	dep[u] = dis[u] = 0,par[u] = u;
	mindis[0] = 0;
	mapp[++tot] = u;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v])continue;
		pretot = tot;
		dis[v] = edge[i].w;
		dep[v] = 1;
		get_dis(v,u,v);
		for(int j = pretot+1;j <= tot;j++){
			int x = mapp[j];
			if(k - dis[x] >= 0)ans = min(ans,mindis[k - dis[x]] + dep[x]);
		}
		for(int j = pretot+1;j <= tot;j++){
			int x = mapp[j];
			if(dis[x] < maxn)mindis[dis[x]] = min(mindis[dis[x]],dep[x]);
		}
	}
	for(int i = 1;i <= tot;i++){
		int j = mapp[i];
		if(dis[j] < maxn)mindis[dis[j]] = INF;
	}
}
void Divide(int u){
	vis[u] = 1;
	dis[u] = 0;
	dep[u] = 0;
	Cal(u);
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v])continue;
		root = 0;
		get_root(v,-1,siz[v]);
		Divide(root);
	}
}
signed main(){
	// freopen("P4149_1.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(head,-1,sizeof(head));
	for(int i = 0;i < maxn;i++)mindis[i] = INF;
	ans = INF;
	cin >> n >> k;
	for(int i = 1;i < n;i++){
		int f,t,w;
		cin >> f >> t >> w;
		f++;t++;
		addedge(f,t,w);
		addedge(t,f,w);
	}
	get_root(1,-1,n);
	Divide(root);
	if(ans == INF)ans = -1;
	cout << ans;
	return 0;
}

虚树

虚树(auxiliary tree)主要用来解决一类树形dp问题. 这类树形dp每次求解只需考虑树中的部分点(称为关键点). 一棵虚树包含全部的关键点以及任意两个关键点之间的LCA. 可以证明 $k$ 个关键点生成的虚树大小不大于 $2 k$ .

vector<pair<int,int> >G[maxn],G2[maxn];//G2为虚树
int dfn[maxn],clk;
void dfs(int u,int fa){
	dfn[u] = ++clk;
	for(auto [v,ww]:G[u])if(v != fa){
		w[v] = min(w[u],ww);
		dfs(v,u);
	}	
}
bool aux_cmp(int u,int v){
	return dfn[u] < dfn[v];
}
vector<int>del_tree;//这里包含了虚树中的所有点
void addedge(int f,int t){
	//在此实现虚树加边
}
void build_aux_tree(vector<int> & key){
	for(int x:del_tree)G2[x].clear(),G2[x].shrink_to_fit();
	del_tree.clear();
	vector<int>stk;
	stk.push_back(1);
	sort(ALL(key),aux_cmp);
	for(int u:key){
		if(stk.size() == 1){
			stk.push_back(u);
			continue;
		}
		int x = stk.back();
		int lca = LCA(u,x);
		if(lca == x){
			stk.push_back(u);
		}
		else{
			while(stk.size() > 1){
				stk.pop_back();
				int y = stk.back();
				if(dfn[y] > dfn[lca]){
					addedge(y,x);
					x = y;
				}
				else if(dfn[y] == dfn[lca]){
					addedge(lca,x);
					break;
				}
				else{
					addedge(lca,x);
					stk.push_back(lca);
					break;
				}
			}
			stk.push_back(u);
		}
	}
	if(stk.size() > 1){
		int x = stk.back();
		while(stk.size() > 1){
			stk.pop_back();
			addedge(stk.back(),x);
			x = stk.back();
		}
	}
}

题意

思路

解法1

解法2

解法3

代码

题面:

思路

代码

题意

思路

代码

题意

思路

代码