图论算法All in one

1. 最长路/最短路

1.1 拓扑求解

首先去判断入度为0的点，然后将入度为0的点加入到队列，遍历队列中的点进行数据的更新，
如果一个点的入度也变为0,那么此时将这个点加入到队列，直到最终的队列为空，所有的点完成了更新。

注意这种解法只能适用于DAG（有向无环图！！！）

1.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
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 <vector>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
using namespace std;
#define mp make_pair
#ifdef limit
#define N 1010
#endif 
#define road 
#ifdef road 
#define N 301010
struct node {
    int to;
    int next;
    int dis;
}E[N];
int head[N], cnt;
void add(int from ,int to, int dis) {
    E[++cnt].next = head[from];
    E[cnt].to = to;
    E[cnt].dis = dis;
    head[from] = cnt;
}
#endif 

#ifdef BFS
int dx[] = {-1, 1, 0, 0 };
int dy[] = {0, 0, -1, 1};
#define tox = (x + dx[i])
#define toy = (y + dy[i])
#endif
int n, m;
void TopSort(vector<int>&in, vector<int>&dis, vector<bool>&vis) {
    queue<int>q;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) q.push(i);
    }
    while (q.size()) {
        int now = q.front();
        q.pop();
        for (int i = head[now]; i; i = E[i].next) {
            in[E[i].to]--;
            if (vis[now]) {
               if (dis[E[i].to] < dis[now] + E[i].dis) dis[E[i].to] = dis[now] + E[i].dis;
               vis[E[i].to] = 1;
            }
            if (in[E[i].to] == 0) q.push(E[i].to);
        }
    }
}
int main() {
   scanf("%d%d", &n, &m); 
   vector<bool>vis(n+1, 0);
   vector<int>in(n+1, 0);
   for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d",&x, &y, &z);
        add(x, y, z);
        in[y]++;
   }
   vector<int>dis(n+1, 0);
   dis[n] = -1;
   vis[1] = 1;
   TopSort(in, dis, vis);
   printf("%d\n",dis[n]);
}

1.1.2 树上最长路

树上最长路又可以被称为是树上路径。

假设一个点为此时的根节点R，直径两点为A, B，如果A, B在R的两个不同的子树，那么必然是经过R。

如果A, B在两个相同的子树，那么A点必然在最远的点，假设不是距离R最远的点，必然可以找到一个距离更远的进行更新。

跑两遍最长路即可。

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
int d[N];
vector<int>v[N];
int n, m;
int BFS(int now) {
    for (int i = 1; i <= n; i++) d[i] = 1e9;
    queue<int>q;
    d[now] = 0;
    q.push(now);
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        for (int i = 0; i < v[top].size(); i++) {
            int to = v[top][i];
            if (d[to] > d[top] + 1) {
                d[to] = d[top] + 1;
                q.push(to);
            }
        }
    }
    int maxn = 0;
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        if (Max < d[i]) {
            Max = d[i];
            maxn = i;
        }
    }
    return maxn;
}
int main() {
   scanf("%d",&n) ;
   for (int i = 1; i < n; i++) {
       int x, y;
       scanf("%d%d", &x, &y);
       v[x].push_back(y);
       v[y].push_back(x);
   }
   printf("%d\n", d[BFS(BFS(1))]);
}


1.1.3 最短路

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
int n ,m ,s;
void TopSort(vector<int>&in, vector<int>&dis, vector<bool>&vis) {
    queue<int>q;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) q.push(i);
    }
    while (q.size()) {
        int now = q.front();
        q.pop();
        for (int i = head[now]; i; i = E[i].next) {
            in[E[i].to]--;
            if (vis[now]) {
               if (dis[E[i].to] > dis[now] + E[i].dis) dis[E[i].to] = dis[now] + E[i].dis;
               vis[E[i].to] = 1;
            }
            if (in[E[i].to] == 0) q.push(E[i].to);
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    vector<int>in(n+1, 0);
    vector<bool>vis(n+1, 0);
    vector<int>dis(n+1, 2e8);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        in[y]++;
    }
    vis[1] = 1;
    dis[1] = 0;
    TopSort(in, dis, vis);
    for (int i = 1; i <= n; i++) printf("%d ",dis[i]);
}

1.2 dijstra算法

dijstra的算法就是维护一群最短的通路，然后进行更新，更新完将最短的新点更新到最短群中。
当一个数据进行更新时，那么此时能够更新它的数据一定已经更新了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dij() {
   vector<bool>vis(n+1, 0);
   vector<long long>dis(n+1,(1ll<<31)-1);
   dis[s] = 0;
   priority_queue<pair<int, int>,vector<pair<int,int>>, greater<pair<int,int>>>q;
   q.push(mp(0, s));
   while (q.size()) {
        int top = q.top().second;
        q.pop();
        if (vis[top]) continue;
        vis[top] = 1;
        for (int i = head[top]; i; i = E[i].next) {
            int to = E[i].to;
            if (dis[to] > dis[top] + E[i].dis) {
                dis[to] = dis[top] + E[i].dis;
                q.push(mp(dis[to], to));
            }
        }
   }
   for (int i = 1; i <= n; i++) printf("%lld ",dis[i]);
}

1.3 最短路统计

基于迪杰斯特拉算法进行统计，当一个距离被更新时，将其路径数更新为其前节点
当新增一条最短路时，增加路径数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dij(vector<bool>&vis) {
    ans[1] = 1;
   while (!q.empty())  {
        auto top = q.top();
        q.pop();
        if (vis[top.second]) continue;
        vis[top.second] = 1;
        int now = top.second;
        for (int i = head[top.second]; i; i = E[i].next) {
            int to = E[i].to;
            if (dis[to] > dis[now] + E[i].dis) {
                dis[to] = dis[now] + E[i].dis;
                ans[to] = ans[now];
                if (!vis[to]) q.push(mp(dis[to], to));
            }
            else if (dis[to] == dis[now] + E[i].dis) {
                ans[to] += ans[now];
            }
        }
   }
   if (!ans[n]) printf("No answer\n");
   else printf("%d %d\n",dis[n], ans[n]);
}

2. 树上问题

对于树上问题，前面在树上最长路的时候有所提及

2.1 LCA

倍增做法

倍增的做法其实很简单，得到每个节点的向上2i2^i层的父节点，在求解LCA的时候，先将两个点移动到
同一层，再向上进行探索，得到第一个相同的父节点。

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
int fa[N][22], dep[N], lg[N];
vector<int>v[N];
void getdep(int root, int fath) {
    dep[root] = dep[fath] + 1; fa[root][0] = fath;
    for (int i = 1; i <= lg[dep[root]]; i++) {
        fa[root][i] = fa[fa[root][i-1]][i-1];
    }
    for (int i = 0; i < v[root].size(); i++)  {
        if (v[root][i] != fath)
        getdep(v[root][i], root);
    }
}
int LCA(int x, int y) {
   if (dep[x] < dep[y]) swap(x, y);
   while (dep[x] > dep[y]) {
        int level = lg[dep[x] - dep[y]];
        x = fa[x][level - 1];
   }
   if (x == y) return x;
   for (int k = lg[dep[x]] - 1; k >= 0; k--) {
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k];
            y = fa[y][k];
        }
   }
   return fa[x][0];
}
int n, m, s;
int main() {
    scanf("%d%d%d",&n,&m, &s);
    for (int i = 1; i <= n; i++) lg[i] = lg[i-1] + (1<<lg[i-1]==i);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d",&x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    getdep(s, 0);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d",&x, &y);
        printf("%d\n", LCA(x, y));
    }
}