[模板]图论

Posted on Edited on In

[TOC]

建图

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

(慎用) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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\)).

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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\)的最大流, 设\(flow_1\) = \((t_i,s_i,\infin)\)边的流量并判断是否存在可行流. 如果存在就把这条边删掉, 再在残余网络上跑一次从\(s_i\)到\(t_i\)的最大流\(flow_2\). 答案即为\(flow_1 + flow2\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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\)的最大流, 答案为\(flow_1- flow_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\)为路径条数最少的路径覆盖. 方案可从流量网络中还原.

建图:

1
2
3
4
5
6
7
8
9
10
11
12
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);

求方案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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(nm)\)

match[v]为\(v\)的匹配点.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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开始. 有空改成自己的板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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即为所求点集:

1
2
3
4
5
6
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(nm)\), 适用于比较小的图.

全局变量: bool unne[]. \(unne[i] = 1\)表示\(i\)为非必经点.

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

1
2
3
4
5
6
7
8
9
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).

1
2
3
4
5
6
7
8
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\)是非必经点.

连通性与环

割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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]);
			}
		}
	}
}

桥

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

\(dp[u]\)表示跨过\(u\)的反向边的数量.如果\(dp[u] == 0\)则\(<fa,u>\)为桥(\(fa\)是\(u\)的父亲)

调用时需初始化\(dep[root] = 1\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}

仙人掌

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

\(backcnt\)为全局变量,初始化为\(n+1\)(点的个数+1)

\(phash[u]\)返回环的标号,从\(n+1\)开始.若不在环内则\(phash[u] == u\)

调用时初始化\(dep[root] = 1\),注意缩点后需要重新寻找根节点(缩点代码未给出)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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)\) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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求最小环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 是的我知道这个变量起的很弱智 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//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,\ldots ,v_n\) 为 \(1,2,\ldots ,n\) 的一个排列，满足 \(v_i\) 在 \(\{v_i,v_{i+1},\ldots ,v_n\}\) 的导出子图中为单纯点.

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

最大势算法(MCS)

优先队列做法

已弃用, 有可能RE

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

输入: \(n\), 点数

\(head[],edge[],cnt\), 无向图(全局变量)

使用的全局变量:\(vis[]\)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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},\ldots , v_n}\) 中相邻的点从小到大为 \(\{v_{c_1},v_{c_2},\ldots ,v_{c_k} \}\)，则只需判断 \(v_{c_1}\) 与其他点是否直接连通即可

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

输出: 该序列是否合法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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,\ldots ,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\ge \chi(G)\)。由于团上每个点都是不同的颜色，所以 \(t=\omega(G)\)，由 Lemma 1，\(t=\omega(G)\le \chi(G)\)。综上，可得 \(t=\chi(G)=\omega(G)\)。

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

树

最小生成树

结论

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

Prim

\(dis[i]\)表示第\(i\)条树边的长度,标号从\(2\)到\(n\).

\(d[i][j]\)为边\(<i,j>\)权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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整个树的过程中, 第一次访问或回溯时均记录下经过的节点即为欧拉序. 例:

image-20211109105112159

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
		}
	}
}

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

欧拉序可将一棵树映射为一维的区间. \([fir[u],lst[u]]\)之间的欧拉序对应的是以\(u\)为根的子树的区间.

求解LCA

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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序

image-20211109105112159

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

一棵大小为\(n\)的树DFS序长度为\(2n\).

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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\)后剩余连通分量的最大值, \(rt\)为树的重心

树最多有两个相邻的重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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的和.

1
2
3
4
5
6
7
8
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\)在独立集里的最优答案.

1
2
3
4
5
6
7
8
9
10
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(mlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
		}
	}
}

也可以用递归写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

判断无根树是否同构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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\)的点对个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//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的最短路径长度(边数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//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\)个关键点生成的虚树大小不大于\(2k\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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();
		}
	}
}