Home Archive Trending Tags Category Friends About Me
KarL05/Aiyiyi's Blog
Blog
Tony Wu
Archive Trending Tags Category Friends About Me
Proudly published with Hexo
Theme Journal. by Makito
© 2025 KarL05/Aiyiyi's Blog
图论模板
  folder 代码Code label 中文Chinese, 归档Archived, 信竞OI

模板整合 - 图论

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void build (int n) {
    for (int i=1;i<=n;i++) fa[i] = i;
}
int finds (int x) {
    if (fa[x]==x) return x;
    fa[x] = finds(fa[x]);
    return fa[x];
}
void merge (int u, int v) {
    int fu = finds(u);
    int fv = finds(v);
    if (fu==fv) return;
    fa[fu] = fa[fv];
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void topography () {
    queue<int> q;
    for (int i=1;i<=cter;i++) {
        if (!ind[i]) q.push(i);
    }
    while (!q.empty()) {
        int cur = q.front();
        last = cur;
        q.pop();
        for (int i=0;i<after[cur].size();i++) {
            int to = after[cur][i];
            ind[to]--;
            if (!ind[to]) q.push(to);
        }
    }
}

最小生成树

  • Kruskal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void kruskal () {
  sort(E+1,E+1+lim,cmp);
  short cnt = 0;
  double ans = 0;
  for (int i=1;i<=lim;i++) {
      int u = F(E[i].u); 
      int v = F(E[i].v);
      if (u==v) continue;
      f[u] = v;
      cnt++;
      //TODO
      if (cnt==n-1) break;
  }
}
  • Prim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
priority_queue<int,vector<pair<double,int> >,greater<pair<double,int> > > q;
void prim() {
	for(int i=2;i<=n;i++) dis[i] = 1e9+7;
	q.push(make_pair(0,1));
	while (!q.empty()) {
		int u = q.top().second; q.pop();
		if (vist[u]) continue;
		vist[u] = 1;
		++cnt;
		ans += dis[u];
		for(int i=1;i<=n;i++) {
            double d = dis(u,i);
		    if (d<dis[i]) {
                dis[i] = d;
                q.push(make_pair(dis[i],i));
            }
		}
		if (cnt==n) break;
	}
}
  • Boruvka
    1. 计算每个点分别属于哪个连通块。将每个连通块都设为“没有最小边”。
    2. 遍历每条边 (u,v) ，如果 u 和 v 不在同一个连通块，就用这条边的边权分别更新 u 和 v 所在连通块的最小边。
    3. 如果所有连通块都没有最小边，退出程序，此时的图就是原图最小生成森林的边集。否则，将每个有最小边的连通块的最小边加入图，返回第一步。
    4. 本质上就是每次维护一些联通块, 然后遍历边, 使得联通块数量折半
mst-1

最短路径/差分约束

  • Dijkstra
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
struct heap {
    int dis,pos;
};
struct cmp {
	bool operator() (heap &a, heap &b) {
		return a.dis>b.dis;
	}
};
int dist[maxn];
int vis[maxn];
void Dijkstra (int a) {
    priority_queue<heap,vector<heap>,cmp> q;
    memset(dist,0x3f,sizeof(dist));
    dist[a] = 0;
    q.push({0,a});
    vis[a] = true;
    while (!q.empty()) {
        int id = q.top().pos;
        q.pop();
        vis[id] = true;
        for (int i=0;i<edges[id].size();i++) {
            edge npos = edges[id][i];
            if (vis[npos.to]) continue;
            if (dist[npos.to]>dist[id]+npos.w) {
                dist[npos.to]=dist[id]+npos.w;
                q.push({dist[npos.to],npos.to});
            }
        }
    }
}
  • Floyd
1
2
3
4
5
6
7
8
9
for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) {
        if (f[i][k]+f[k][j]<f[i][j]) {
            f[i][j] = f[i][k]+f[k][j];
            cnt[i][j] = cnt[i][k]*cnt[k][j];
        }
        else if (f[i][k]+f[k][j]==f[i][j]) {
            cnt[i][j] += cnt[i][k]*cnt[k][j];
        }
}
  • Bellman - Ford
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
int spfa (int s) {
    for (int i=1;i<=n;i++) dis[i] = -1;    
    queue<int> q;
    inq[s] = 1;
    dis[s] = 0;
    cnt[s]++;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();q.pop();
        // cout<<u;
        inq[u] = 0;
        for (int i=0;i<E[u].size();i++) {
            int v = E[u][i].v;
            int w = E[u][i].w;
            if (dis[v]<dis[u]+w) {
                dis[v] = dis[u]+w;
                if (!inq[v]) {
                    inq[v] = 1;
                    cnt[v]++;
                    q.push(v);
                    if (cnt[v]>n) return 0;
                }
            }
        }
    }
    return 1;
}
  • 最小斯坦纳树
    • 要引入外部点, 使用状态压缩动态规划
  • 最小树形图
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
#include"bits/stdc++.h"
using namespace std;
const int maxn = 105;
const int maxm = 10005; 
struct edge {
    int u,v,w;
}e[maxm];
int n,m,root,mn[maxn],fa[maxn],tp[maxn],lp[maxn],tot,ans;
int zl() {
	while (233) {
		for(int i=1;i<=n;i++) {
            mn[i] = 1e9;
            fa[i] = tp[i] = lp[i] = 0;
        }
		for(int i=1,u,v,w;i<=m;i++) if(e[i].u!=e[i].v&&(w=e[i].w)<mn[v=e[i].v]) {
			mn[v] = w;
            fa[v] = e[i].u;
        }
		mn[root] = 0;
		for(int u=1;u<=n;u++){
            ans += mn[u];
            if (mn[u]==1e9) return -1;
        } 
		for (int u=1,v=1;u<=n;u++,v=u) { 
			while (v!=root&&tp[v]!=u&&!lp[v]) {
                tp[v] = u;
                v = fa[v];
            }
			if (v!=root&&!lp[v]) { 
				lp[v] = ++tot;
				for (int k=fa[v];k!=v;k=fa[k]) lp[k] = tot;
			}
		}
		if (!tot) return ans; 
		for (int i=1;i<=n;i++) if(!lp[i]) lp[i] = ++tot; 
		
		for (int i=1;i<=m;i++) {
			e[i].w -= mn[e[i].v];
            e[i].u = lp[e[i].u];
            e[i].v = lp[e[i].v];
        }
		n = tot;
        root = lp[root];
        tot = 0; 
	}
}

int main(){
	cin>>n>>m>>root;
	for(int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        e[i] = {u,v,w};
    }	
	cout<<zl()<<endl;
	return 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
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using std::cout;
using std::cin;
using std::ios;
using std::vector;
using std::queue;
using std::stack;

void prepare () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

const int maxn = 1e5+5;
int min[maxn];
int max[maxn];
int ind[maxn];
int val[maxn];
int dp[maxn];
int mn[maxn];
int n,m;
vector<int> edges[maxn];
vector<int> after[maxn];
int dfn[maxn];
int low[maxn];
int sizes[maxn];
int belong[maxn];
int instack[maxn];
int pter, cter;
stack<int> st;
queue<int> q;

void tarjan (int pos)
{
	dfn[pos] = low[pos] = ++pter;
	instack[pos] = 1;
    st.push(pos);
	for (int i=0;i<edges[pos].size();i++)
	{
		int npos = edges[pos][i];
		if (!dfn[npos]) {
			tarjan(npos);
			low[pos] = std::min(low[pos],low[npos]);
		}
		else if (instack[npos]) {
            low[pos] = std::min(low[pos],low[npos]);
        }
	}
	if (dfn[pos]==low[pos]) {
		cter++;
		while (st.top()!=pos) {
			instack[st.top()] = 0;
			belong[st.top()] = cter;
            sizes[cter]++;
            st.pop();
		}
        instack[st.top()] = 0;
        belong[st.top()] = cter;
        sizes[cter]++;
        st.pop();
	}
}

int main () {
    prepare();
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>val[i];
    for (int i=1;i<=m;i++) {
        int a,b,c;
        cin>>a>>b>>c;
        if (c==1) {
            edges[a].push_back(b);
        }
        else {
            edges[a].push_back(b);
            edges[b].push_back(a);
        }
    }
    memset(mn,0x3f,sizeof(mn));
    for (int i=1;i<=n;i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i=1;i<=n;i++) {
        for (int j=0;j<edges[i].size();j++) {
            int to = edges[i][j];
            if (belong[i]==belong[to]) continue;
            int a = belong[i];
            int b = belong[to];
            after[a].push_back(b);
            ind[b]++;
        }
    }
    memset(min,0x3f,sizeof(min));
    for (int i=1;i<=n;i++) {
        min[belong[i]] = std::min(min[belong[i]],val[i]);
        max[belong[i]] = std::max(max[belong[i]],val[i]);
    }
    for (int i=1;i<=n;i++) {
        if (!ind[i]) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int at = q.front();
        q.pop();
        mn[at] = std::min(mn[at],min[at]);
        for (int i=0;i<after[at].size();i++) {
            int to = after[at][i];
            ind[to]--;
            dp[to] = std::max(dp[to],max[to]-mn[at]);
            dp[to] = std::max(dp[to],max[to]-min[to]);
            dp[to] = std::max(dp[to],dp[at]);
            if (!ind[to]) q.push(to);
        }
    }
    // for (int i=1;i<=cter;i++) {
    //     cout<<dp[i]<<" "<<max[i]<<" "<<min[i]<<" "<<mn[i]<<std::endl;
    // }
    cout<<dp[belong[n]]<<std::endl;
    return 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
#include"bits/stdc++.h"
const int maxn = 1e6+5;
using namespace std;

struct edge
{
    int to,pre;
}edges[maxn];
int head[maxn],dfn[maxn],dfs_clock,tot;
int num;
int st[maxn],top;
vector<int>bcc[maxn];
int cnt[maxn];
int key[maxn];

void clear (int n) {
    for (int i=1;i<=n;i++) head[i] = 0;
    for (int i=1;i<=tot;i++) edges[i].to = edges[i].pre = 0;
    tot = 0;
    for (int i=1;i<=n;i++) {
        dfn[i] = 0;
        st[i] = 0;
        bcc[i].clear();
    }
}
int tarjan (int u,int fa) {
    int lowu = dfn[u] = ++dfs_clock;
    int child = 0;
    for (int i=head[u];i;i=edges[i].pre) {
        if(!dfn[edges[i].to])
        {
            child++;
            st[++top] = edges[i].to;
            int lowv = tarjan(edges[i].to,u);
            lowu = min(lowu,lowv);
            if (fa!=u&&lowv>=dfn[u]&&!key[u]) {
                key[u] = true;
            }
            if (lowv>=dfn[u]) {
                num++;
                while (st[top]!=edges[i].to) bcc[num].push_back(st[top--]);
                bcc[num].push_back(st[top--]);
                bcc[num].push_back(u);
            }
        }
        else if (edges[i].to!=fa) lowu = min(lowu,dfn[edges[i].to]);
    }
    if (fa==u&&child>=2&&!key[u]) key[u] = true;
    return lowu;
}
void add(int x,int y)
{
    edges[++tot].to = y;
    edges[tot].pre = head[x];
    head[x] = tot;
}
int main() {
    while (true) {
        int n;cin>>n;
        if (!n) exit(0);
        clear(n);
        for (int i=1;i<=n;i++) {
            int x,y;
            cin>>x>>y;
            add(x,y);add(y,x);
        }
        for (int i=1;i<=n;i++) {
            if (!dfn[i]) {
                st[top=1] = i;
                tarjan(i,i);
            }
        }
        for (int i=1;i<=num;i++) {
            for (int j=0;j<bcc[i].size();j++) {
                if (key[bcc[i][j]]) cnt[i]++; 
            }
        }
        int ans = 0;
        int val = 1;
        for (int i=1;i<=num;i++) {
            int sz = bcc[i].size()-cnt[i];
            if (cnt[i]==0) {
                ans += 2;
                val *= sz*(sz-1)/2;
            }
            if (cnt[i]==1) {
                ans += 1;
                val *= sz;
            }
        }
        cout<<ans<<" "<<val<<endl;
    }
    return 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
#include"bits/stdc++.h"
typedef long long ll;
using namespace std;

const ll inf = 1e15;
int n,m,s,t;
const int maxn = 6e5;
ll dis[maxn];
int tot = 1;
int now[maxn];
int head[maxn]; 

struct node {
	int to,net;
	ll val;
} e[maxn];

void add (int u,int v, ll w) {
	e[++tot].to = v;
	e[tot].val = w;
	e[tot].net = head[u];
	head[u] = tot;

	e[++tot].to = u;
	e[tot].val = 0;
	e[tot].net = head[v];
	head[v] = tot;
}

int bfs () {  
	for (int i=1;i<=n;i++) dis[i] = inf;
	queue<int> q;q.push(s);
	dis[s] = 0;
	now[s] = head[s];
	while (!q.empty()) {
		int x = q.front();q.pop();
		for(int i=head[x];i;i=e[i].net) {
			int v = e[i].to;
			if (e[i].val>0&&dis[v]==inf) {
				q.push(v);
				now[v] = head[v];
				dis[v] = dis[x]+1;
				if(v==t) return 1;
			}
		}
	}
	return 0;
}

ll dfs (int x,ll sum) { 
	if (x==t) return sum;
	ll k,res=0; 
	for(int i=now[x];i&&sum>0;i=e[i].net) {
		now[x] = i;  
		int v = e[i].to;
		if (e[i].val>0&&(dis[v]==dis[x]+1)) {
			k = dfs(v,min(sum,e[i].val));
			if(k==0) dis[v] = inf; 
			e[i].val -= k;
            e[i^1].val += k;
			res += k;
            sum -= k; 
		}
	}
	return res;
}

int main() {
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++) {
        int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
    ll ans = 0;
	while (bfs()) ans += dfs(s,inf); 
	cout<<ans<<endl;
	return 0;
}

二分图

  • 将图分为两部分, 考虑两部分之间的边
  • 使用Dinic网络流可以解决二分图匹配 时间复杂度 O(n√n)
  • 有显然的二类特性的问题大多数可以考虑二分图

2-SAT

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
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int maxn = 2e6+5;

vector<int> edges[maxn];
vector<int> after[maxn];
int dfn[maxn];
int low[maxn];
int sizes[maxn];
int belong[maxn];
int instack[maxn];
int pter, cter;
stack<int> st;
queue<int> q;
int n,m;

void tarjan (int pos)
{
	dfn[pos] = low[pos] = ++pter;
	instack[pos] = 1;
    st.push(pos);
	for (int i=0;i<edges[pos].size();i++)
	{
		int npos = edges[pos][i];
		if (!dfn[npos]) {
			tarjan(npos);
			low[pos] = min(low[pos],low[npos]);
		}
		else if (instack[npos]) {
            low[pos] = min(low[pos],low[npos]);
        }
	}
	if (dfn[pos]==low[pos]) {
		cter++;
		while (st.top()!=pos) {
			instack[st.top()] = 0;
			belong[st.top()] = cter;
            sizes[cter]++;
            st.pop();
		}
        instack[st.top()] = 0;
        belong[st.top()] = cter;
        sizes[cter]++;
        st.pop();
	}
}

void prepare () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main () {
    prepare();
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        edges[a+n*b].push_back(c+n*(d^1));
        edges[c+n*d].push_back(a+n*(b^1));
    }
    for (int i=1;i<=n+n;i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i=1;i<=n;i++) {
        if (belong[i]==belong[i+n]) {
            cout<<"IMPOSSIBLE"<<endl;
            return 0;
        }
    }
    cout<<"POSSIBLE"<<endl;
    for (int i=1;i<=n;i++) {
        cout<<(belong[i]<belong[i+n])<<" ";
    }
    cout<<endl;
}
  • 矩阵树定理
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
#include"bits/stdc++.h"
using namespace std;

const int MOD = 1e4+7;
const int maxn = 505;
int graph[maxn][maxn];
int n,m,t;

int det(int n) {
	int f = 1;
	int res = 1;
	for (int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			graph[i][j] += MOD;
			graph[i][j] %= MOD;
		}
	}
	for (int i=1;i<=n;i++) {
		for(int j=i+1;j<=n;j++) {
			int x = graph[i][i];
			int y = graph[j][i];
			while (y) {
				int tmp = x/y;
				x %= y;
				swap(x,y);
				for (int k=i;k<=n;k++) {
					graph[i][k] = (graph[i][k]-tmp*graph[j][k])%MOD;
					graph[i][k] += MOD;
					graph[i][k] %= MOD;
				}
				for (int k=i;k<=n;k++) swap(graph[i][k],graph[j][k]);
				f *= -1;
			}
		}
		if (!graph[i][i]) return 0;
		res *= graph[i][i];
		res %= MOD;
	} 
	if (f==-1) res = MOD-res;
	res %= MOD;
	res += MOD;
	return res;
}

int main () {
    int m;
    cin>>n>>m;
    n--;
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        u--;v--;
        graph[u][u] = (graph[u][u]+1)%MOD;
        graph[u][v] = (graph[u][v]-1+MOD)%MOD;
    }
    cout<<det(n)%MOD<<endl;
}

BEST 定理 \[ ec(G) = \det(G')\prod_{v\in V} (\text{deg}(v)-1)! \]

Proudly published with Hexo
Theme Journal. by Makito
© 2025 KarL05/Aiyiyi's Blog