图论模板

包括了一些简单的图论内容,不含网络流

树与图的存储

邻接矩阵：mp[a][b]mp[a][b] 存储边 a→ba \rightarrow b

邻接表：

1
2
3
4
5
6
7
8
9
10
11
12
int head[MAXN];//表头
int tot;//边的总数
struct EDGE {
    int to, next, val;
}edge[MAXM];
void add_edge(int from,int to,int val) {
    //添加一条边
    edge[++tot].to = to; edge[tot].val = val; edge[tot].next = head[from]; head[from] = tot;
} 
//初始化
tot = 0;
memset(head, 0, sizeof head);

树与图的遍历

时间复杂度 O(n+m)O(n+m) nn 表示点数 ，mm 表示边数

深度优先遍历：

1
2
3
4
5
6
7
8
int vis[MAXN];//标记某个点有没有被遍历过
void dfs(int now) {
    vis[now] = 1;
    for(int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (!vis[to]) dfs(to);
    }
}

宽度优先遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int vis[MAXN];//标记某个点有没有被遍历过
void bfs(int s) {
    queue<int> q;
    vis[s] = 1;//标记起点
    q.push(s);
    while (!q.empty()) {
        int now=q.front(); q.pop();
        for (int i = head[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            if (!vis[to]) {
                vis[to] = true;//表示to已经被遍历过
                q.push(to);
            }
        }
    }
}

树的直径

树形DP做法：

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
int n, ans;
const int N = 1e4 + 10;
int f[N];
struct node {
    int v;int w;
};
vector<node> ve[N];

int dfs(int u, int pre) {
    int dis = 0;
    int d1 = 0, d2 = 0;
    for (node i : ve[u]) {
        if (i.v == pre) continue;
        int d = dfs(i.v, u) + i.w;
        dis = max(dis, d);
        if (d >= d1) {
            d2 = d1, d1 = d;
        }
        else if (d > d2) d2 = d;
    }

    ans = max(ans, d1 + d2);
    return dis;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    int u, v, w;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
    }

    dfs(1, 0);
    printf("%d\n", ans);

    return 0;
}

两次DFS：

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
int n;
const int N = 1e4 + 10;
int dis[N];
struct node {
    int v;int w;
};
vector<node> ve[N];

void dfs(int u, int pre) {
    for (node i : ve[u]) {
        if (i.v == pre) continue;
        dis[i.v] = dis[u] + i.w;
        dfs(i.v, u);
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    int u, v, w, t, res;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
    }
    dis[1] = 0;
    dfs(1, 0);
    t = -1, res = -1;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] > res) {
            res = dis[i], t = i;
        }
    }
    dis[t] = 0;
    dfs(t, 0);
    t = -1, res = -1;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] > res) {
            res = dis[i], t = i;
        }
    }
    printf("%d\n", res);

    return 0;
}


树的中心

在树中找到一个点，使得该点与树中其他点的最远距离最近

树形DP

进行两次树形dp
以任意结点为根，对于结点i来说，离它最远的点有2种可能，一是向下走遇到最远点（此时最远点为i的孩子）；
二是向上走（可能先向上走再向下走）遇到最远点（此时最远点不是它的孩子）。

  1. down[i]: 以i为两条路径的最高点，求最长路径和次长路径，以及最长路径所在的子节点;
  2. up[i]: 从i开始向上走，离最远点的距离;
  3. f[i] = max(down[i], up[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
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
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;
const int N = 1e4 + 10;
struct dist {
    int d1, d2, inx;
};
dist down[N];
struct node {
    int v, w;
};
vector<node> ve[N];
int up[N], f[N];

int dfs(int cur, int pre) {
    int d1 = 0, d2 = 0, inx = 0;
    for (node i : ve[cur]) {
        if (i.v == pre) continue;
        int d = dfs(i.v, cur) + i.w;
        if (d > d1) {
            inx = i.v, d2 = d1, d1 = d;
        }
        else if (d > d2) {
            d2 = d;
        }
    }
    down[cur] = dist{d1, d2, inx};
    return d1;
}

void dp(int cur, int pre, int d) {
    int inx = down[pre].inx, d1 = down[pre].d1, d2 = down[pre].d2;
    up[cur] = up[pre] + d;
    if (inx == cur) {
        up[cur] = max(up[cur], d2 + d);
    }
    else {
        up[cur] = max(up[cur], d1 + d);
    }
    f[cur] = max(up[cur], down[cur].d1);
    for (node i : ve[cur]) {
        if (i.v == pre) continue;
        dp(i.v, cur, i.w);
    }
}

int main(void) {
    int u, v, w;
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
    }

    dfs(1, 0);
    dp(1, 0, 0);

    int res = 1e9 + 10;
    for (int i = 1; i <= n; ++i) {
        res = min(res, f[i]);
    }
    cout << res << endl;

    return 0;
}


图的直径

用 floydfloyd 。floydfloyd 能求出任意两点间的距离，取最值就行。

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
ll n, m;
ll dis[505][505];
void init() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
}

void solve() {
    n = read(), m = read();
    init();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        dis[u][v] = 1;
        dis[v][u] = 1;
    }
    ll ans = 0;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans = max(ans, dis[i][j]);
    printf("%lld\n", ans);
    
}

最小环相关

DFS树求无向图最小环

将图看成一颗“树”，利用深度和 dfsdfs 遍历树的性质求解。正常 dfsdfs 遍历时，总是由深度小的点往深度大的点更新，而环的存在就导致可能在某一点能够回到其祖先节点。这样环的长度即为 depth[now]−depth[to]+1depth[now] - depth[to] + 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
int n, m;
int depth[MAXN];//点的深度
int fa[MAXN];//前驱
int mn = INF;//最小环长度
int start = 0;//打印环用

void dfs(int now, int pre) { //求解最小环问题
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        if (depth[to] != 0 && depth[now] - depth[to] + 1 < mn) { 
            //这条边连向了祖先节点,说明是个环。深度跨距表示环的长度，说明当前小于最小环
            if (depth[now] - depth[to] + 1 < 0) continue; //由于是无向边+树的遍历，这种情况是存在的
            mn = depth[now] - depth[to] + 1;
            start = now;
        }
        else if(!depth[to]) {
            fa[to] = now;
            depth[to] = depth[now] + 1;
            dfs(to, now);
        }
    }
}

void output() { //打印最小环
    printf("%d\n", mn); //先输出最小环的长度
    int now = start;
    for (int i = 1; i <= mn; i++) {
        printf("%d ", now);
        now = fa[now];
    }
}

void solve() {
    depth[1] = 1; //初始化
    dfs(1, 0);
    output();
}

floyd求无向图最小环

在每次以顶点 kk 为中间点求得完最短路后，再循环更新两点间的最小回路。

最小环权值数组 dis[i][j]dis[i][j] ，已知的权值数组 a[i][j]a[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//初始化
#define INF 0x3f3f3f3f
int ans = INF;
memset(dis, 0x3f, sizeof(dis));
memset(a, 0x3f, sizeof(a));

//输入图中两点边权a[i][j]

for (int k = 1; k <= n; k++) {
    for (int i = 1; i < k; i++)
        for (int j = i + 1; j < k; j++)
            ans = min(ans, dis[i][j] + a[i][k] + a[k][j]);
    //答案为i到j的最短路径权值加上j到k的边权和i到k的边权
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    //更新i到j的最短路径
}

并查集求有向图最小环长度

当并查集找祖先找到自己的时候，说明出现了环。可以在查找祖先的同时记录下遍历的次数，当最后找到自己的时候与当前最小环的长度进行比较，看是否需要更新。注意： 这条边不用相连，否则会进入死循环。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200005
int ans = 0x3f3f3f3f;//最小环的个数
int f[MAXN];
ll n;
int cnt;
int findx(int x, int &cnt) {
    cnt++;
    if (x == f[x]) return x;
    else return findx(f[x], cnt);
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= n; i++) {
        int temp;
        cnt = 0;
        cin >> temp;
        int goal = findx(temp, cnt);
        if (goal == i) {
            ans = min(ans, cnt);
        }
        else f[i] = temp;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

有向带权图的最小环

枚举每一个点作为起点，在松弛完起点所有的出边后把起点的 disdis 重置为 INFINF ，visitvisit 重置为 falsefalse 。之后再扫到该起点时该起点的 disdis 为最小环。堆优化后复杂度为 O(n(n+m)logn)O(n(n+m)logn)

这是另一种做法：

根据题目的特殊要求，当存在一个环的边权和小于等于c是返回1否则返回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
int dij(int s) {
    for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0;
    dis[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({dis[s], s});
    while (q.size()) {
        int now = q.top().second;
        q.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for (int i = head[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            ll val = edge[i].val;
            if (to == s && dis[now] + val <= c) return 1;
            if (dis[to] > dis[now] + val) {
                dis[to] = dis[now] + val;
                q.push({dis[to], to});
            }
        }
    }
    return 0;
}

for (int i = 1; i <= n; i++) {
        int tmp = dij(i);
        if (tmp == 1) {
            ans++;
            break;
        }
    }

正常求最小环的话应该遍历起始点，然后每次找到一个环就和当前的就好了

拓扑排序

时间复杂度 O(n+m)O(n+m) ， nn 表示点数，mm 表示边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int indgr[MAXN];//记录有向图的入度数
void topu() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!indgr[i])//将入度数为0的点推入队列
            q.push(i);
    while (!q.empty()) {
        int now = q.front(); q.pop();
        for (int i = head[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            //进行相关操作
            if (--indgr[to] == 0)
                q.push(to);
        }
    }
}

最短路相关

朴素 dijkstra 算法

时间复杂度 O(n2+m)O(n^2+m) ，nn 表示点数，mm 表示边数

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
#define INF 0x3f3f3f3f
int mp[MAXN][MAXN];//存储每条边
int dis[MAXN];//存储一号点到每个点的最短距离
int vis[MAXN];//存储每个点的最短路是否已经确定
//求一号点到n号点的最短距离，如果不存在返回-1

void init() {
    for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
            if (i == j) mp[i][j] = 0;
    		else mp[i][j] = INF;
}

int dij(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for(int i = 0; i < n - 1; i++) {
        int t = -1;//在还未确定最短路的点中，寻找距离最小的点
        for(int j = 1; j <= n; j++)
            if(!vis[j] && (t == -1 || dis[t] > dis[j]))
        		t=j;
        
        for (int j = 1; j <= n; j++)
            dis[j] = min(dis[j], dis[t] + mp[t][j]);//用t更新其他点的最短距离
        
        vis[t] = 1;
    }
    if (dis[n] == INF) return -1;
    return dis[n];
}

堆优化dijkstra

时间复杂度 O(mlogn)O(mlogn) , nn 表示点数 , mm 表示边数

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
#define INF 0x3f3f3f3f
typedef pair<int,int> pii;
int n;//点的数量
int dis[MAXN];//存储所有点到一号点的距离
int vis[MAXN];//存储每个点的最短距离是否已经确定

//求一号点到n号点的最短距离，如果不存在，则返回-1
int dij(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    priority_queue<pii> q;
    q.push({dis[s], s});
    while (!q.empty()) {
        int now = q.top().second; q.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for(int i = head[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            int val = edge[i].val;
            if(dis[to] > dis[now] + val) {
                dis[to] = dis[now] + val;
                q.push({-dis[to], to});
            }
        }
    }
    if(dis[n] == INF) return -1;
    return dis[n];
}

超级源点与超级终点

多用于图中有多个源点和多个终点的情况

如果有多个起点，跑 kk 遍算法很容易超时，这时建立一个超级源点，与所有起点连一条权值为 00 的边，单单对这个点进行操作。超级终点也是如此

最短路方案计数问题

在松弛里做一些操作。如果dis[to]==now+val，则方案数累加；如果dis[to]>dis[now]+val，则用新的方案替代原先的方案

求次短路

在松弛里做一些操作。如果可以更新最短路，则更新最短路，原最短路变为次短路；若可更新次短路，则更新次短路。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
ll n, m;
struct node {
    ll val;
    int u, v;
}a[MAXM];
ll dis[MAXN];

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        ll w = read();
        a[i] = {-w, u, v};
    }
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    for (int i = 1; i <= n; i++) {
        for (int i = 1; i <= m; i++) {
            ll val = a[i].val;
            int u = a[i].u;
            int v = a[i].v;
            if (dis[v] > dis[u] + val) {
                dis[v] = dis[u] + val;
            } 
        }
    }
    ll ans = dis[n];
    for (int i = 1; i <= m; i++) {
        ll val = a[i].val;
        int u = a[i].u;
        int v = a[i].v;
        if (dis[v] > dis[u] + val) {
            dis[v] = dis[u] + val;
        }
    }
    if (dis[n] != ans) //n号节点的负环中
        puts("inf");
    else
        printf("%lld\n", -ans);
}
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;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge {
    // 边，a表示出点，b表示入点，w表示边的权重
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

SPFA

时间复杂度 平均情况下 O(m)O(m) ，最坏情况下 O(nm)O(nm) ，nn 表示点数 ，mm 表示边数

求 ss 到 nn 的最短距离，如果无法走到输出 −1-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
#define INF 0x3f3f3f3f
int n;//总点数
int dis[MAXN];//存储每个点到s的最短距离
int vis[MAXN];//存储每个点是否在队列中
int spfa(int s) {
    queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; vis[s] = 1; q.push(s);
    while (!q.empty()) {
        int now = q.front(); q.pop();
        vis[now] = 0;
        for (int i = head[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            int val = edge[i].val;
            if (dis[to] > dis[now] + val) {
                dis[to] = dis[now] + val;
                if (!vis[to]){
                    //如果队列中已存在to，则不需要将to重复插入
                    q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }
    if (dis[n] == INF) return -1;
    return dis[n];
}

最长路

SPFA可以处理负权边，所以还可以较简单的求最长路。一开始将dis重置为负无穷大，松弛操作时候的再取反即可。或者一开始直接将所有边权取反，跑一遍SPFA的最短路模板

SPFA判负环

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
#define INF 0x3f3f3f3f
int n;//总点数
int dis[MAXN];//存储每个点到s的最短距离
int vis[MAXN];//存储每个点是否在队列中
int cnt[MAXN];//存储1到x的最短路中经过的点数
bool spfa(int s) { 
    //如果存在负环，返回true；否则返回false
    queue<int> q;
   	//不需要初始化dis数组
    for (int i = 1; i <= n; i++) {
        q.push(i);
        vis[i] = 1;
    }
    while (!q.empty()) {
        int now = q.front(); q.pop();
        vis[now] = 0;
        for (int i = head[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            int val = edge[i].val;
            if (dis[to] > dis[now] + val) {
                dis[to] = dis[now] + val;
                cnt[to] = cnt[now] + 1;
                if (cnt[to] >= n) return true;//一条路径上包含至少n个点说明存在环
                if (!vis[to]) {
                    q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }
    return false;
}

SPFA判正环

同样，SPFA判正环只需将松弛操作的符号反一下即可。

差分约束系统

如果一个系统由 nn 个变量和 mm 个不等式组成，并且这 mm 个不等式均为 xi−xj≤a[k]x_i - x_j \leq a[k] 的形式，这样的系统成为 差分约束

求最大值，跑最短路；求最小值，跑最长路。

最短路求完后任意三角关系满足：dis[to]≤dis[now]+mp[now][to]dis[to] \leq dis[now] + mp[now][to]

最长路求完后任意三角关系满足：dis[to]≥dis[now]+mp[now][to]dis[to]\geq dis[now] + mp[now][to]

now→tonow \rightarrow to 连一条权值为 mp[now][to]mp[now][to] 的边。

需要提前通过乘以负号等操作使得所有不等式 符号相同 以进行最短/长路的进一步操作。只能用 SPFASPFA 。

有唯一解 是最简单的一种情况，源点 SS 到终点 EE 之间存在最短路。

如果源点 SS 到终点 EE 不存在最短路，即存在 负环 ，就可以表示为方程的 无解情况 。

如果源点 SS 根本无法到达终点 EE ，即 dis[E]=INFdis[E]=INF，表示 SS 和 EE 之前不存在约束关系，表示为方程的 多解情况 。

  1. 求差值的最大值，全部转化为 x−y≤zx-y \leq z 这种格式；求差值的最小值，全部转化为 x−y≥zx-y \geq z 这种形式
  2. 如果有形如 x−y=zx-y=z 的形式，将其变化成两个不等式：x−y≤zx-y \leq z 和 x−y≥zx-y \geq z
  3. 如果有形如 x−y<zx-y<z 的形式，将其变化为 x−y≤z−1x-y \leq z-1 的形式

为了得到正确的结果，我们必须保证至少存在一个点，通过这个点我们可以遍历所有的 边 。（注意不是点，下文会说明）。

边是我们在图论中的理解，回到求不等式解的问题当中。遍历不到某条边就相当于无法保证满足不等式组中的所有约束，答案就可能产生错误。

遍历不到某个点没有任何关系，说明其没有任何约束，随便取什么值都可以。

如果可以通过某个点走到任意点上，那么也可以通过该点走过任何边。（边是连接点和点的，必然可以通过所有边）

具体实现时，往往在原图上附加一个超级源点，这个顶点与每个顶点连上一条权值为 00 的边。

这里有一个有趣的结论，我们从 00 到 ii 加了一条边，转化成不等式就相当于 xi≤x0x_i\leq x_0 ，xix_i 在图里又相当于从源点到 ii 的最短路大小，x0x_0 在图中又意味着源点。也就是说，当我们一开始就把 x0x_0 的解定为X时，所有未知数的解都不会大于X（dis[0]=X）

线性约束 一般是在一维空间中给出一些变量（一般定义位置），然后告诉你某两个变量的约束关系，求两个变量 aa 和 bb 差值的最大值或最小值。

区间约束 一般是给出一些区间，要求对于[ai,bi][a_i,b_i] 这个区间，区间内的数字大于/不大于/小于/不小于 cic_i 。然后问在这个约束条件下整数集合最少包含多少数。

先看看我们已知的限制条件，对于一个区间 [l,r][l,r] ，∑i=li=r≥ci\sum_{i=l}^{i=r}\geq c_i ，这很明显不符合差分约束的不等式格式。考虑转化成前缀和去做。这就变成了 sum[r]−sum[l−1]≥cisum[r]-sum[l-1] \geq c_i 。

定义单位最大值为MAX。

同时，一定要记住，前缀和还有这两个性质。sum[i]≥sum[i−1]sum[i] \geq sum[i-1] ，sum[i]−sum[i−1]≤MAXsum[i]-sum[i-1]\leq MAX 。有了这两个性质就能保证是连通图了。**注意：转化成前缀和后0这个点必须存在。**如果不存在需要其他点需要自增。

未知条件约束 是指在不等式的右边不一定是个常数，可能是个未知数。可以通过枚举或者二分这个未知数，把未知数变成已知数，通过判断方程组是否有解来判断枚举的这个数是否可行。

floyd相关

floyd

时间复杂度为 O(n3)O(n^3)，nn 表示点数

1
2
3
4
5
6
7
8
9
10
11
12
#define INF 0x3f3f3f3f
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (i == j) dis[i][j] = 0;
		else dis[i][j] = INF;
//算法结束后，dis[i][j]表示i到j的最短距离
void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for( int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

floyd求传递闭包

1
2
3
4
5
//mp[i][j]表示图中i和j是否连通
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1;j <= n; j++)
            mp[i][j] |= mp[i][k] & mp[k][j];

最小生成树相关

朴素版prim求最小生成树

时间复杂度 O(n2+m)O(n^2+m) ，nn 表示点数，mm 表示边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define INF 0x3f3f3f3f
int n;//n表示点数
int mp[MAXN][MAXN];//邻接矩阵，存储所有边
int dis[MAXN];//存储其他点到最小生成树的距离
int vis[MAXN];//存储每个点是否已经在生成树中

//如果图不连通则返回INF，否则返回最小生成树的树边权重之和
int prim() {
    memset(dis, 0x3f, sizeof(dis));
    int res = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)      
            if (!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        if (i && dis[t] == INF) return INF;
        if (i) res += dis[t];
        vis[t] = 1;
        for(int j = 1; j <= n; j++)
            dis[j] = min(dis[j], mp[t][j]);
    }
    return res;
}

Kruskal求最小生成树

时间复杂度为 O(mlogm)O(mlogm) ，nn 表示点数，mm 表示边数

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
#define INF 0x3f3f3f3f
int n, m;//n表示点数，m表示边数
int f[MAXN];//并查集的父节点数组
struct EDGE {
    int a, b, w;
    bool operator< (const EDGE &W) const {
        return w < W.W;
    }
}edge[MAXM];

int findx(int x) {
    if (x == f[x]) return x;
    return f[x] = findx(f[x]);
}

int kruskal() {
    sort(edge + 1, edge + 1 + m);
    for (int i = 1; i <= n; i++) f[i] = i;//初始化并查集
	int res = 0, cnt = 0;
    for (int i = 1; i <= m; i++) {
        int x = edge[i].a, y = edge[i].b, w = edge[i].w;
        x = findx(x), y = findx(y);
        if (x != y) {
            f[y] = x;
            cnt++;
            res += w;
        }
    }
    if (cnt < n - 1) return INF;
    return res;
}

LCA相关

倍增求LCA

预处理时间复杂度 O(nlogn)O(nlogn) ，单次查询时间复杂度 O(logn)O(logn)

f[i][j]f[i][j] 表示从 ii 向上走 2j2^j 次步的节点的编号 0≤j≤logn0 \leq j \leq logn

depth[i]depth[i] 表示节点 ii 的深度，默认根节点的深度为 11 。节点 ii 的深度=与根节点的距离+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
int n, m, rt;//点数，边数，根
int depth[MAXN];//点的深度
int fa[MAXN][25];

void build(int rt) {
    //预处理fa数组
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0;//哨兵
    depth[rt] = 1;
    queue<int> q;
    q.push(rt);
    while (!q.empty()) {
        int now = q.front(); q.pop();
        for (int i = head[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            if (depth[to] > depth[now] + 1){
                //to还没搜索过
                depth[to] = depth[now] + 1;
                q.push(to);
                fa[to][0] = now;//to的上一层为now
                for (int k = 1; k <= 24; k++) {
                    fa[to][k] = fa[fa[to][k-1]][k-1];//向上更新
                }
            }
        }
    }
}

int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 24; k >= 0; k--) {
        //跳到相同的深度
        if (depth[fa[x][k]] >= depth[y])
            x = fa[x][k];
    }
    if (x == y) return x;
    for (int k = 24; k >= 0; k--) {
        //一起往上跳
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k];
            y = fa[y][k];
        }
    }
    return fa[x][0];
}

void solve() {
    build(rt);
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) <<endl;
    }
}

Tarjan离线算法求LCA

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

在深度优先搜索时将所有点分为三大类：

  • 还未遍历过的点 蓝
  • 正在搜索中的分支（从根节点到当前节点的一条路径） 红
  • 已经回溯完的点 绿

红色的点和绿色的点的 LCALCA 就是并查集意义中绿色点的代表元素。通过维护并查集就可以求出两个点的 LCA 。只要在 dfsdfs 的时候维护并查集即可，维护的复杂度为 O(n)O(n)。

建图部分（包括连边和记录查询方案）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i = 1; i < n; i++) {
    //连边
    int u, v, w;
    cin >> u >> v >> w;
    add_edge(u, v, w);
    add_edge(v, u, w);
}
// vector <pii> mp[MAXN] first表示另一个点的编号，second表示方案的编号
for (int i = 1; i <= m; i++) {
    //记录查询方案
    int u, v;
    cin >> u >> v;
    if (u != v) {
        mp[u].push_back({v, i});
        mp[v].push_back({u, i});
    }
}

然后对任意点跑一个 tarjantarjan

1
tarjan(1);

tarjantarjan 算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void tarjan(int now) {
    vis[now] = 1; //表示正在搜索这个点
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (!vis[to])
            tarjan(to), f[to] = now; //合并到根节点
    }
    for (auto x : mp[now])  {
        //遍历和该点相关的所有查询方案
        int to = x.first;
        int tim = x.second;
        if (vis[to] == 2)  {
            //该点已完成回溯,LCA为f[to]
            int fa = findx(to);
            ans[tim] = dis[now] + dis[to] - 2 * dis[fa];
        }
    }
    vis[now] = 2; //该点已完成回溯
}

Tarjan算法求强连通分量

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
int n, m;                      //点数和边数
int head[MAXN], h[MAXN];       //如果有需要，h表示原图的表头，head表示求完强连通分量后的表头
int low[MAXN], dfn[MAXN], num; //时间戳相关定义
int vis[MAXN];
stack<int> st;       //栈相关定义
int key[MAXN];       //标记每个点属于哪个强连通分量
int scc, sccc[MAXN]; //强连通分量个数和强连通分量要维护的东西
void tarjan(int x) {
    low[x] = dfn[x] = ++num; //更新时间戳
    st.push(x);
    vis[x] = 1; //入栈
    for (int i = h[x]; i; i = edge[i].next) {
        int y = edge[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (vis[y] == 1) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (low[x] == dfn[x]) {
        scc++;
        int now = -1;
        while (now != x) {
            now = st.top();
            st.pop();
            vis[now] = 0; //出栈标记
            key[now] = scc;
            sccc[scc]++; //维护强连通分量size
        }
    }
}

void solve() {
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
}

对于DAG图而言，通过所有入度数为 00 的点即可遍历到所有的点。

对于DAG图而言，至少需要加 max(入度数为0的点的个数, 出度数为0的点的个数) 条边，就能使得这张图成为强连通分量。

连通分量相关

强连通分量逆序求拓扑

tarjantarjan 的强连通分量的求解顺序的逆序是一个拓扑序。可以通过倒着遍历强连通分量编号的写法来代替宽搜拓扑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//以最长链方案统计为例
for (int now = scc; now; now--) {
    if (!dp[now])
        dp[now] = sccc[now], cnt[now] = 1;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        int val = sccc[to];
        if (dp[to] == dp[now] + val) {
            cnt[to] = (cnt[to] + cnt[now]) % mod;
        }
        else if (dp[to] < dp[now] + val) {
            dp[to] = dp[now] + val;
            cnt[to] = cnt[now];
        }
    }
}

缩点

把环看成一个点进行后面的算法。一般缩点后的点权是环路中所有点的点权和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n;
int key[MAXN];
int h[MAXN];    //原图
int head[MAXN]; //新图
void solve() {
    for (int now = 1; now <= n; now++) {
        for (int i = h[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            if (key[now] == key[to])
                continue;                      //如果两端属于一个强连通分量放弃连边
            add_edge(head, key[now], key[to]); //将两个点对应的强连通分量编号连边
            //单点也属于强连通分量
        }
    }
}

这是遍历点，也可以遍历边。如果一条边的两个端点不是属于两个强连通分量，就在新图上连一条边。

缩点哈希判重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
set<ll> s;
for (int now = 1; now <= n; now++) {
    for (int i = hh[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (key[now] == key[to])
            continue;
        ll hash = key[now] * 1000000ll + key[to];
        if (s.count(hash))
            continue; //判重边
        add_edge(head, key[now], key[to]);
        indgr[key[to]]++;
        s.insert(hash);
    }
}

边双连通分量

对于一张连通的无向图，如果删除图中的某条边之后原先的图不能成为连通图，那么这条边就被称为 桥

极大的不包含桥的连通块，被称为 边双连通分量（e-dcc）

对于边双连通分量，不管删除哪条边，图依旧是连通的。

  • 如何判断桥？

    ​ 判断 yy 能否走到 xx 的祖先节点！！！如果不能，则为桥。

    dfn(x)<low(y)dfn(x)<low(y)

  • 如何找到所有边双连通分量？

    ​ 利用栈维护，如果dfn(x)==low(x)dfn(x)==low(x) ，表示 xx 无法返回他的祖先节点，说明 xx 的父节点与 xx 的边即为桥，还在栈当中的节点即为边双连通分量。

对于一棵树，所有边都是桥。

写的时候因为是无向边，我们要新加一个参数 prepre (prepre 是边不是点)防止走回头路，因为如果走回头路的话必然找不到桥了。

要新开一个数组 bridge[MAXN]bridge[MAXN] 来记录每条边是否是桥。如果一条边是桥，那么他的反向边也是桥。

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
int n, m;                       //点数，边数
int num, dfn[MAXN], low[MAXN];  //时间戳相关
int dcc, key[MAXN], dccc[MAXN]; //边双连通分量相关
stack<int> st;
vis[MAXN];        //栈
int bridge[MAXM]; //判断某条边是不是桥，1表示是

void init() {
    memset(head, 0, sizeof(head));
    tot = 0;
    memset(bridge, 0, sizeof(bridge));
    memset(vis, 0, sizeof(vis));
    memset(dfn, 0, sizeof(dfn));
    num = 0;
    dcc = 0;
}

int get(int x) {
    //求反向边
    if (x & 1)
        return x + 1;
    return x - 1;
}

void tarjan(int x, int pre) {
    dfn[x] = low[x] = ++num;
    st.push(x);
    vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next) {
        int y = edge[i].to;
        if (!dfn[y]) {
            tarjan(y, i); //从i这条边走过来的
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x])  {
                // y无法返回x的祖先
                bridge[i] = bridge[get(i)] = 1;
            }
        }
        else if (i != get(pre)) //这条路不是回头路且时间戳更新过
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        dcc++;
        int now = -1;
        while (now != x) {
            now = st.top();
            st.pop();
            vis[now] = 0;
            //维护边双连通分量相关信息
            key[now] = dcc;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    tarjan(1, 0);
    int flag = 1; //整个图是不是连通图

    for (int i = 1; i <= n; i++)  {
        //有点未更新时间戳表示图不连通
        if (!dfn[i]) {
            flag = 0;
            break;
        }
    }

    for (int i = 1; i <= tot; i++)
        if (bridge[i]) //对所有桥进行操作
}

结论：对于一个无向连通图，将图中所有的双连通分量缩点后，定义那些度数为 11 的点个数为 cntcnt 。则最少需要添加 (cnt+1)/2(cnt+1)/2 条边，就能使原图变为双连通分量。

桥的缩点

桥的缩点其实好写一点。边的信息要记录两端。已知缩点后的图是一棵树，所有的树边都是桥。所以在判完所有桥后，遍历每条边。若该边是桥，就在新图上把两个端点代表的 keykey 值连条边。

1
2
3
4
5
6
for (int i = 1; i <= tot; i += 2) {
    if (bridge[i]) {
        add_edge(h, key[edge[i].u], key[edge[i].v]);
        add_edge(h, key[edge[i].v], key[edge[i].u]);
    }
}

点双连通分量

如果删除图中的某个点与和他连的边之后原先的图不能成为连通图，那么这个点就被称为 割点

对于一个连通块 uu ，如果不存在另一个连通块 vv ，使得 vv 包含 uu 中所有的元素并且 vv 含有 uu 中没有的元素，称 uu 是极大的。

每一个割点至少属于两个连通分量。

每一个点双连通分量至少包含一个割点。

依旧引入 时间戳 的概念

  • 如何求割点？

还是类似，由 xx 连向 yy ，去掉 xx 和与之相连的边后，yy 不能返回 xx 的祖先节点。但如果 xx 是整个图的根节点，那么还得继续讨论

  1. xx 不是根节点，dfn[x]≤low[y]dfn[x] \leq low[y]
  2. xx 是根节点，满足 xx 至少有两个子节点 y1,y2y_1,y_2 ，使得low[y1]≥dfn[x]ANDlow[y2]≥dfn[x]low[y_1]\geq dfn[x] AND low[y_2]\geq dfn[x]
  • 如何维护所有点双连通分量

还是需要一个栈。

当发现 dfn[x]≤low[y]dfn[x] \leq low[y] 时，说明 yy 无法返回 xx 的祖先节点，说明原图中点双连通分量的个数 vccvcc 加一。如果 xx 不是根节点或者 cnt>1cnt>1 ，说明 xx 是割点。此时就将栈中元素弹出直至弹出 yy 。并且 xx 也属于该点双连通分量。

特判一下一个孤立点的情况，因为这也算一个点双连通分量。

缩点步骤：

  1. 每个割点单独作为一个点
  2. 每个点双连通分量向它所包含的那个割点连条边

这样操作完之后，每个点双连通分量的度数就是其所连接的割点的个数。

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
int n, m;                      //点数和边数
int dfn[MAXN], num, low[MAXN]; //时间戳相关
int dcc;
vector<int> dccc[MAXN];
stack<int> st;
int iscut[MAXN];  //判断是否为割点
int root;         //遍历时随机选择的根节点
int cnt_unpassed; //连通块数量个数
void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    int cnt = 0;                   //删除该点，原先的一个连通块变成cnt个连通块
    if (x == root && head[x] == 0) {
        //特判孤立点
        dcc++;
        dccc[dcc].emplace_back(x);
        return;
    }
    for (int i = head[x]; i; i = edge[i].next) {
        int y = edge[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y])  {
                // y无法到达x的祖先
                cnt++;
                if (x != root || cnt > 1)
                    iscut[x] = 1; // x是割点
                dcc++;
                int now = -1;
                while (now != y) {
                    now = st.top();
                    st.pop();
                    dccc[dcc].emplace_back(now);
                }
                dccc[dcc].emplace_back(x); //把x也要push进去
            }
        }
        else
            low[x] = min(low[x], dfn[y]);
    }
}

void solve() {
    for (root = 1; root <= n; root++) {
        if (!dfn[root]) {
            cnt_unpassed++; //连通块个数+1
            tarjan(root);
        }
    }

    for (int i = 1; i <= dcc; i++) {
        int cnt = 0; //统计一个点双连通分量内的割点个数
        for (int j = 0; j < dccc[i].size(); j++) {
            if (iscut[dccc[i][j]] == 1) //如果是割点
                cnt++;
        }
    }
}

二分图相关

染色法判断二分图

一个图的顶点可以分为两个集合 XX 和 YY ，图的所有边一定是有一个顶点属于 XX ，另一个顶点属于集合 YY ，则称该图为 二分图 。

二分图当且仅当图中不含 奇数环 。

由于图中不含奇数环，所以染色过程中一定没有矛盾。如果能完美地将一张图的所有点染色成功，即为二分图；如果产生矛盾，则不是二分图。

时间复杂度 O(n+m)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
int n, m;                //点数，边数
int color[MAXN];         //表示每个点的颜色，-1表示还未染色
bool dfs(int now, int c) {
    // x表示点编号，c表示颜色
    color[now] = c;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (color[to] == -1) {
            if (!dfs(to, !c)) //搜完后出现了矛盾
                return false;
        }
        else if (color[to] == c) //之前的结果和现在的结果产生矛盾
            return false;
    }
    return true;
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (!dfs(i, 0))  {
                //染色时出现了矛盾
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

二分图染色的过程中只要合法，染什么颜色都是无所谓的，到最后颜色是互补的。可以利用这个性质记录下来两种颜色的个数的和。然后根据题目的具体条件将颜色人为分配为较小的或较大的。就像下面这样

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int j = 0; j <= 30; j++) {
    memset(color, -1, sizeof(color));
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (!dfs(i, j, 0)) {
                cout << -1 << endl;
                return;
            }
        }
        ans += base[j] * min(sum0, sum1);
        sum0 = 0, sum1 = 0;
    }
}

二分图的最大匹配

具体可以理解成男女婚配问题，给出一些男女之间的爱慕关系，求出情侣的最多数量。遍历所有其中一个集合的人，如果发现他喜欢的人都心有所属，那么一个个绿过去，看看她原来的对象能否找到一个新的女朋友。如果能找到，就绿了他；如果不能，说明这个人注孤生。

经过 NN 趟 DFSDFS ，匹配到另一个集合的尚未匹配的人就结束当前搜索，开始下一趟搜索。

最坏时间复杂度 O(nm)O(nm) 即遍历所有边，实际运行时间一般远小于 O(nm)O(nm) 。

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
int n, nn, m;    // n表示第一个点集中的点数，nn表示第二个点集中的点数
int vis[MAXN];   // vis表示第二个集合中的某个点是否已经被遍历过
int match[MAXN]; // match表示第二个集合中的某个点当前匹配的第一个集合中的点是哪个
int ans = 0;     //最大匹配数

bool find(int now) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (!vis[to]) {
            //如果这个now可能的对象还未搜索过 
            vis[to] = 1;                           //标记一下，防止重复搜索
            if (match[to] == 0 || find(match[to])) {
                //如果她当前还没对象或者可以绿她的对象
                match[to] = now;
                return true;
            }
        }
    }
    return false;
}

void solve() {
    for (int i = 1; i <= n; i++) {
        //跑N趟DFS 
        memset(vis, 0, sizeof(vis));
        if (find(i))
            ans++;
    }
    cout << ans << endl;
}

最小点覆盖

结论：最大匹配数=最小点覆盖

给出一张图，选出最少的点，使得每条边的两个端点至少有一个被选出来。

在 二分图 中，最小点覆盖=最大匹配数。

最大独立集

从一个图中选出最多的点，使得选出的点之间是没有边相连的。

在 二分图 中，最大独立集=点数-最大匹配

从定义下手，相当于在一个图中去掉最少的点，将所有边都破坏掉。

也就等价于，找到最少的点，使得这些点能覆盖所有的边。

DAG图的最小路径点覆盖

对于一张DAG图，选出最少的互不相交的边使得其能覆盖图中所有的点。

在二分图中，最小路径覆盖数=顶点数-最大匹配

因为无法确保DAG图是二分图，所以要拆点，就像种类并查集那样扩大原先的数组为 22 倍。

左边的点称为 出点 ，右边的点称为 入点 ，每次从左边连到右边。这样就能确保一定是二分图。

此时将原图中的路径互不相交，所以每一个点最多只有一个出度和入度，这就意味着在新图中，左部每一个点最多连出一条边，右边的点最多连入一条边，每个点最多只会属于一条边。

此时

  • 原图中的路径 对应 新图中的一组匹配
  • 原图中每一条路径的终点 对应 新图左部的非匹配点

总结：

求原图中互不相交路径数 求路径终点数最少 求左部分非匹配点最少 求最大匹配

最小路径重复点覆盖

在最小路径覆盖问题的基础上，去掉互不相交。

模板题：求一遍传递闭包后跑一下匈牙利算法求最大匹配。答案就是 n−ansn-ans

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
int n, nn, m;    // n表示第一个点集中的点数，nn表示第二个点集中的点数
int vis[MAXN];   // vis表示第二个集合中的某个点是否已经被遍历过
int match[MAXN]; // match表示第二个集合中的某个点当前匹配的第一个集合中的点是哪个
int ans = 0;     //最大匹配数

bool find(int now) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (!vis[to]) {
            //如果这个now可能的对象还未搜索过
            vis[to] = 1; //标记一下，防止重复搜索
            if (match[to] == 0 || find(match[to])) {
                //如果她当前还没对象或者可以绿她的对象
                match[to] = now;
                return true;
            }
        }
    }
    return false;
}

void solve() {
    for (int i = 1; i <= n; i++) {
        //跑N趟DFS
        memset(vis, 0, sizeof(vis));
        if (find(i))
            ans++;
    }
    cout << ans << endl;
}

欧拉路径与欧拉回路

基本概念：

欧拉路径：图中的一条路径，能够通过图中的每一条边，并且每条边仅通过一次

欧拉回路：就是闭合的欧拉路径

欧拉图：包含欧拉回路的图

判断：

无向图（连通）

  • 欧拉路径：度数为奇数的点只能有 00 个或 22 个。
  • 欧拉回路：度数为奇数的点只能有 00 个。

有向图（连通）

  • 欧拉路径：要么所有点的出度均等于入度；要么除了两个点之外，其余所有点的入度等于出度。剩余的两个点一个点满足 出度-入度=1 （起点），另一个满足 入度-出度=1 （终点）。
  • 欧拉回路：所有点的出度均等于入度

算法实现：

利用 dfsdfs 来找到一条欧拉回路。

以无向图为例，因为每个点的度都为偶数，所以我们从任意一个点出发，假设所有点的度数都为 22 ，那么 dfsdfs 一定会回到起点，从而形成一个回路。

如果度数都为 22 ，那么现在就是一条欧拉回路；假设度数不全为 22 ，有 4,6,84,6,8 …那么在 dfsdfs 过程中，当走到这些点(假设走到点 nownow )上时，可能会走到其他环上，但是由于度数是偶数，所以如果走到其他环上，最后也会回到点 nownow 。

在 dfsdfs过后，一定会形成许多环，环与环之间有一个交点，在回溯过程中将这些点添加到答案中，就是一条欧拉回路。
有向图同理。

概括：分三步，删边，爆搜，记录答案（路径）

有向图和无向图的欧拉回路

模板题：给出一张图，给出它是有向或无向，求一条欧拉回路

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
int type;                     //有向图 or 无向图
int n, m;                     //点,边的数量
int ans[MAXM], cnt;           //记录欧拉回路用，必须是边的数量
int vis[MAXM];                //标记某条边有没有走过
int indgr[MAXN], oudgr[MAXN]; //点的入度和出度来表示度数

void dfs(int now) {
    //判重删边，dfs，记录答案
    for (int &i = head[now]; i;) {
        //改变引用后就能直接删边了 
        if (vis[i]) {
            //这条边用过了 
            i = edge[i].next; //删除这条边
            continue;
        }
        vis[i] = 1;
        if (type == 1) //如果是无向边，反向边也要标记删除
            vis[get(i)] = 1;
        int id;        //表示边的编号
        if (type == 1) {
            //无向图
            id = (i + 1) / 2;
            if (i % 2 == 0) //本题特有的脑瘫条件，不用管
                id = -id;
        }
        else //有向图
            id = i;
        int j = edge[i].to;
        i = edge[i].next;
        dfs(j);
        ans[++cnt] = id;
    }
    if (type == 2) {
        //判断度数合法性
        for (int i = 1; i <= n; i++) {
            if (indgr[i] != oudgr[i]) {
                cout << "NO" << endl;
                return;
            }
        }
    }
    else {
        for (int i = 1; i <= n; i++) {
            if ((indgr[i] + oudgr[i]) & 1) {
                cout << "NO" << endl;
                return;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        //找一个非孤立点去遍历整张图 
        if (head[i] != 0) {
            dfs(i);
            break; //一定要break掉，因为有非连通的情况存在
        }
    }
    if (cnt < m) {
        //判断图的连通性
        cout << "NO" << endl;
    }
    cout << "YES" << endl;
    for (int i = cnt; i > 0; i--) //欧拉路要倒着输出
        cout << ans[i] << " ";
    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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 505
#define MAXM 2105
int mp[MAXN][MAXN];
int d[MAXN]; //存储度数
int n, m;
int ans[MAXM], cnt;

void dfs(int now) {
    for (int i = 1; i <= 500; i++) {
        if (mp[now][i]) {
            mp[now][i]--, mp[i][now]--; //删边
            dfs(i);                     //爆搜
        }
    }
    ans[++cnt] = now; //记录答案
}

void solve() {
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        mp[u][v]++, mp[v][u]++;
        d[u]++, d[v]++;
    }
    int start = 0;
    while (!d[start])
        start++; //特判欧拉回路的情况
    for (int i = 1; i <= 500; i++) {
        if (d[i] & 1) {
            //如果是一条欧拉回路前面必须做过处理，否则出不来
            start = i;
            break;
        }
    }
    dfs(start);
    for (int i = cnt; i; i--) //欧拉路要倒着输出
        cout << ans[i] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    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
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
int f[MAXN];
int din[MAXN], dout[MAXN];
int st[MAXN];
int n;
int find(int x) {
    if (x == f[x])
        return x;
    else
        return f[x] = find(f[x]);
}
int g[50][50];

void solve() {
    int n;
    cin >> n;
    memset(st, 0, sizeof st);
    memset(din, 0, sizeof din);
    memset(dout, 0, sizeof dout);
    for (int i = 0; i <= n; i++) {
        f[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        int a = s[0] - 'a', b = s[(int)s.size() - 1] - 'a';
        st[a] = st[b] = 1;
        g[a][b]++;
        dout[a]++, din[b]++;
        int pa = find(a), pb = find(b);
        f[pa] = pb;
    }
    int tmp = -1;
    int res = 0;
    for (int i = 0; i < 26; i++) {
        //图的连通性 
        if (st[i]) {
            if (tmp == -1)
                tmp = find(i);
            else {
                if (tmp != find(i)) {
                    res = 1;
                    break;
                }
            }
        }
    }
    int start = 0, ed = 0;
    for (int i = 0; i < 26; i++) {
        //判断有向图入度出度的合法性
        if (din[i] != dout[i]) {
            if (dout[i] == din[i] + 1)
                start++;
            else if (din[i] - 1 == dout[i])
                ed++;
            else {
                res = 1;
                break;
            }
        }
    }
    if (start != 0 || ed != 0) {
        if (start != 1 || ed != 1)
            res = 1;
    }
    if (res == 1) {
        cout << "The door cannot be opened." << endl;
    }
    else {
        cout << "Ordering is possible." << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

如果要求具体的欧拉路径，判断完连通性和度数合法性后，对最小编号的点进行一遍 dfsdfs 即可，模板套用上两个邻接矩阵或邻接表的模板。