没进水的脑子


——博客——

图论总结

  • ~39.43K 字
  1. 1. 图论总结
    1. 1.1. 图的基本表示方法
      1. 1.1.1. 图的存储方法
    2. 1.2. 图论基础算法
      1. 1.2.1. 最短路
      2. 1.2.2. 拓扑排序
      3. 1.2.3. 最小生成树
      4. 1.2.4. 最近公祖先
      5. 1.2.5. 缩点
        1. 1.2.5.1. 一些有关连通性的基本概念
      6. 1.2.6. 经典算法
      7. 1.2.7. 欧拉路
        1. 1.2.7.1. 定义
        2. 1.2.7.2. 性质
        3. 1.2.7.3. 判别法
        4. 1.2.7.4. 无向图欧拉路求解算法
      8. 1.2.8. 基环树
        1. 1.2.8.1. 基本概念
        2. 1.2.8.2. 解题思路
      9. 1.2.9. 网络流
        1. 1.2.9.1. 解题思路
    3. 1.3. 建图思想
      1. 1.3.1. 同余最短路
        1. 1.3.1.1. 解题思路
      2. 1.3.2. 分层图
      3. 1.3.3. 差分约束
        1. 1.3.3.1. 解题思路
      4. 1.3.4. 2-SAT
      5. 1.3.5. 数据结构优化建图
      6. 1.3.6. 前缀优化建图
      7. 1.3.7. 一些奇奇怪怪的建图
    4. 1.4. 参考资料

图论总结

图的基本表示方法

设 为一张图， 为点集， 为边集，则有

对于每一条边 都有其对应权值 。

图的存储方法

  1. 首先我们可以根据表示方法来写出一种非常直接的存图方法

    Code
    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
    class Node {
        public:
            int id;
            Node(int id = 0) : id(id) {}
    };
    class Edge {
        public:
            int val;
            Edge(int val = 0) : val(val) {}
    };
    class Map {
            Node *node;
            Edge **edge;

        public:
            Map(int NodeSize) {
                node = new Node[NodeSize]();
                edge = new Edge *[NodeSize]();
                for (int i = 0; i < NodeSize; i++)
                    edge[i] = new Edge[NodeSize]();
            }
            void AddEdge(int HeadNode, int ConnectNode, int EdgeVal = 1) {
                edge[HeadNode][ConnectNode] = Edge(EdgeVal);
            }
    };

    我们可以发现在代码中的 变量以一个二维矩阵的形式存在，因此也将其称为邻接矩阵。此类存图方法通常用于存储点数较少的图。

  2. 我们可以借鉴链表的存储方法，将图用链表存储起来，被称为链式前向星。

    Code
    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
    class Edge {
        public:
            int HeadNode;
            int ConnectNode;
            int EdgeVal;
            int Next;
            Edge(int HeadNode = 0, int ConnectNode = 0, int EdgeVal = 0, int Next = 0):
                HeadNode(HeadNode), ConnectNode(ConnectNode), EdgeVal(EdgeVal), Next(Next) {}
    };
    class Map {
            int *Head;
            Edge *edge;
            int edgenumber;
        public:
            Map(int NodeSize, int EdgeSize) {
                Head = new int[NodeSize]();
                edge = new Edge[EdgeSize]();
                edgenumber = 0;
            }
            void AddEdge(int HeadNode, int ConnectNode, int EdgeVal) {
                ++edgenumber;
                edge[edgenumber] = Edge(HeadNode, ConnectNode, EdgeVal, Head[HeadNode]);
                Head[HeadNode] = edgenumber;
            }
    };

  3. 当然我们也可以以点为中心，将该点可以扩展出来的边存在该点中，称为邻接表。

    Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include <vector>
    using namespace std;
    class Edge {
        public:
            int HeadNode;
            int ConnectNode;
            int EdgeVal;
            Edge(int HeadNode = 0, int ConnectNode = 0, int EdgeVal = 0):
                HeadNode(HeadNode), ConnectNode(ConnectNode), EdgeVal(EdgeVal) {}
    };
    class Node {
        public:
            vector<Edge>edge;
    };
    class Map {
            Node *node;
            Map(int NodeSize) {
                node = new Node[NodeSize]();
            }
            void AddEdge(int HeadNode, int ConnectNode, int EdgeVal) {
                node[HeadNode].edge.push_back(Edge(HeadNode, ConnectNode, EdgeVal));
            }
    };

图论基础算法

最短路

  1. SPFA
    一种老少皆宜的最短路算法，由于他简单易懂的代码和十分容易被卡的特性，深受OIer和出题人的喜爱。

     关于SPFA，它死了
    Code
    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
    #include <bits/stdc++.h>
    using namespace std;
    const int inf = INT32_MAX;
    const int N = 1e4 + 10;
    vector<pair<int, int>>g[N];
    int n, m, s;
    int dis[N];
    bool vis[N];
    void spfa() {
        for (int i = 1; i <= n; i++) dis[i] = inf;
        dis[s] = 0;
        queue<int>q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for (auto e : g[u]) {
                int v = e.first;
                int val = e.second;
                if (dis[v] > dis[u] + val) {
                    dis[v] = dis[u] + val;
                    if (!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
    }
    int main() {
        cin >> n >> m >> s;
        for (int i = 1; i <= m; i++) {
            int u, v, val;
            cin >> u >> v >> val;
            g[u].push_back({v, val});
        }
        spfa();
        for (int i = 1; i <= n; i++) cout << dis[i] << " ";
    }
    闲的没事版class封装逆天代码
    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
    #include <vector>
    #include <queue>
    #include <iostream>
    using namespace std;
    class Edge {
        public:
            int HeadNode;
            int ConnectNode;
            int EdgeVal;
            Edge(int HeadNode = 0, int ConnectNode = 0, int EdgeVal = 0): HeadNode(HeadNode), ConnectNode(ConnectNode), EdgeVal(EdgeVal) {}
    };
    class Node {
        public:
            int dis;
            bool vis;
            vector<Edge>edge;
            Node(): dis(0x7fffffff), vis(0) {}
    };
    class Map {
            Node *node;
            int MaxNode;
        public:
            Map(int NodeSize) {
                node = new Node[NodeSize]();
                MaxNode = NodeSize;
            }
            void AddEdge(int HeadNode, int ConnectNode, int EdgeVal) {
                node[HeadNode].edge.push_back(Edge(HeadNode, ConnectNode, EdgeVal));
            }
            void GetShortestCircuitWithSPFA(int StartNode) {
                node[StartNode].dis = 0;
                queue<int>q;
                q.push(StartNode);
                while (!q.empty()) {
                    int NowNode = q.front();
                    node[NowNode].vis = 0;
                    q.pop();
                    for (auto e : node[NowNode].edge) {
                        int NextNode = e.ConnectNode;
                        int EdgeVal = e.EdgeVal;
                        if (node[NextNode].dis <= node[NowNode].dis + EdgeVal) continue;
                        node[NextNode].dis = node[NowNode].dis + EdgeVal;
                        if (node[NextNode].vis) continue;
                        node[NextNode].vis = 1;
                        q.push(NextNode);
                    }
                }
            }
            void OutPutShortestCircuit() {
                for (int i = 0; i < MaxNode; i++) cout << node[i].dis << " ";
            }
    };
    int main() {
        int n, m, s;
        cin >> n >> m >> s;
        Map map(n);
        for (int i = 1, u, v, val; i <= m; i++) cin >> u >> v >> val, map.AddEdge(--u, --v, val);
        map.GetShortestCircuitWithSPFA(--s), map.OutPutShortestCircuit();
    }

  2. Dijkstra
    相较于SPFA来说，Dijkstra有更加稳定的复杂度，虽然在随机数据上比SPFA多一个 ，但至少不那么容易被卡。

    Code
    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
    #include <vector>
    #include <queue>
    #include <iostream>
    using namespace std;
    class Edge {
        public:
            int HeadNode;
            int ConnectNode;
            int EdgeVal;
            Edge(int HeadNode = 0, int ConnectNode = 0, int EdgeVal = 0): HeadNode(HeadNode), ConnectNode(ConnectNode), EdgeVal(EdgeVal) {}
    };
    class Node {
        public:
            int dis;
            bool vis;
            vector<Edge>edge;
            Node(): dis(0x7fffffff), vis(0) {}
    };
    class Map {
            Node *node;
            int MaxNode;
        public:
            Map(int NodeSize) {
                node = new Node[NodeSize]();
                MaxNode = NodeSize;
            }
            void AddEdge(int HeadNode, int ConnectNode, int EdgeVal) {
                node[HeadNode].edge.push_back(Edge(HeadNode, ConnectNode, EdgeVal));
            }
            void GetShortestCircuitWithDijkstra(int StartNode) {
                node[StartNode].dis = 0;
                priority_queue<pair<int, int>>q;
                q.push({0, StartNode});
                while (q.size()) {
                    int NowNode = q.top().second;
                    node[NowNode].vis = 0;
                    q.pop();
                    for (auto e : node[NowNode].edge) {
                        int NextNode = e.ConnectNode;
                        int EdgeVal = e.EdgeVal;
                        if (node[NextNode].dis <= node[NowNode].dis + EdgeVal) continue;
                        node[NextNode].dis = node[NowNode].dis + EdgeVal;
                        if (node[NextNode].vis) continue;
                        node[NextNode].vis = 1;
                        q.push({-node[NextNode].dis, NextNode});
                    }
                }
            }
            void OutPutShortestCircuit() {
                for (int i = 0; i < MaxNode; i++) cout << node[i].dis << " ";
            }
    };
    int main() {
        int n, m, s;
        cin >> n >> m >> s;
        Map map(n);
        for (int i = 1, u, v, val; i <= m; i++) cin >> u >> v >> val, map.AddEdge(--u, --v, val);
        map.GetShortestCircuitWithDijkstra(--s), map.OutPutShortestCircuit();
    }

拓扑排序

某些事件需要其他事件完成后在进行，因此为了解决事件处理的先后问题而引入了拓扑排序，我们可以将当前任务的所有前置任务连向当前任务，然后进行BFS搜索，只有当某一个点的入度为 时才将其插入队列。

Code
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T;
int n, m;
vector<int>g[N];
int in[N];
bool vis[N];
bool used[N];
void work() {
    for (int i = 1; i <= n; i++) g[i].clear(),in[i]=0;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        if (u == v) {
            puts("Impossible!");
            return;
        }
        g[v].push_back(u);
        in[u]++;
    }
    priority_queue<int>q;
    vector<int>out;
    for (int i = 1; i <= n; i++) if (!in[i]) q.push(i);
    while (!q.empty()) {
        int u = q.top();
        out.push_back(u);
        q.pop();
        for (auto v : g[u]) {
            if (!(--in[v])) q.push(v);
        }
    }
    if (out.size() < n) {
        puts("Impossible!");
        return;
    }
    for (int i = out.size() - 1; i >= 0; i--) cout << out[i] << " ";
    puts("");
}
int main() {
    cin >> T;
    while (T--) {
        work();
    }
}

最小生成树

最小生成树即在给定图中保留部分边使图转换成一棵树，并且使得所有边权最小。

  1. Kruskal

    Code
    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
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 5010;
    int n, m;
    int fa[N];
    int find(int x) {
        if (x != fa[x]) fa[x] = find(fa[x]);
        return fa[x];
    }
    void add(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            fa[x] = fa[y];
        }
    }
    const int M = 2e5 + 10;
    struct edge {
        int u, v, val;
    } ed[M];
    bool cmp(edge a, edge b) {
        return a.val < b.val;
    }
    int cnt;
    int ans;
    void Kruskal() {
        for (int i = 1; i <= m; i++) {
            edge now = ed[i];
            if (find(now.v) != find(now.u)) {
                fa[find(now.u)] = find(now.v);
                ans += now.val;
            }
        }
    }
    int main() {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            int aa, bb, cc;
            cin >> aa >> bb >> cc;
            ed[++cnt].u = aa;
            ed[cnt].v = bb;
            ed[cnt].val = cc;
        }
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
        sort(ed + 1, ed + m + 1, cmp);
        Kruskal();
        int aa = 0;
        for (int i = 1; i <= n; i++) {
            if (fa[i] == i)aa++;
            if (aa > 1) {
                cout << "orz";
                return 0;
            }
        }
        cout << ans;
        return 0;
    }

  2. Prim

    Code
    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
    #include<cstdio>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    #define R register int
    using namespace std;

    int k,n,m,cnt,sum,ai,bi,ci,head[5005],dis[5005],vis[5005];

    struct Edge
    {
        int v,w,next;
    }e[400005];

    void add(int u,int v,int w)
    {
        e[++k].v=v;
        e[k].w=w;
        e[k].next=head[u];
        head[u]=k;
    }

    typedef pair <int,int> pii;
    priority_queue <pii,vector<pii>,greater<pii> > q;

    void prim()
    {
        dis[1]=0;
        q.push(make_pair(0,1));
        while(!q.empty()&&cnt<n)
        {
            int d=q.top().first,u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            cnt++;
            sum+=d;
            vis[u]=1;
            for(R i=head[u];i!=-1;i=e[i].next)
                if(e[i].w<dis[e[i].v])
                    dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v));
        }
    }

    int main()
    {
        memset(dis,127,sizeof(dis));
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(R i=1;i<=m;i++)
        {
            scanf("%d%d%d",&ai,&bi,&ci);
            add(ai,bi,ci);
            add(bi,ai,ci);
        }
        prim();
        if (cnt==n)printf("%d",sum);
        else printf("orz");
    }

最近公祖先

一个经典树上问题，就是找两个节点在树上的最近公祖先。

  1. 倍增法

    Code（直接贺了一篇写的很详细的题解）
    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
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    #include<stdio.h>
    #include<vector>
    #define maxn 500500
    using namespace std;
    ///隶属邻接表 
    struct Edge{                    //邻接表的结构体 
        int from,to;
    }edges[2*maxn];                 //边要乘2，因为是无向图 ； 
    int first[maxn],next[2*maxn];   //同理； 
    int read(){                        //读入优化，可以照着这个模板来写，这个还算写的比较好看。 
        int re=0;
        char ch=getchar();
        while (ch<'0' || ch>'9') ch=getchar();
        while (ch>='0' && ch<='9'){ 
            re=re*10+ch-'0'; 
            ch=getchar();
        }
        return re;
    }
    ///////////////////////////////////////////////
    ///全局变量 
    int n,m;
    int root;
    int height[maxn];
    float log2n;
    ///////////////////////////////////////////////////////
    ///隶属LCA的全局变量 
    int f[maxn][20];// 
    int have[maxn];                           //have，有没有找过，这都是套路 。 
    void dfs(int u,int h){                 //u代表点的标号，h代表高度。 
        int v;
        height[u]=h;
        for(int i=1;i<=log2n;i++) {
            if(h<=(1<<i)) break;              //由于i是从小到大计算的，故（1<<i）>=h 时可直接退出。请务必想清楚是<=  还是=。
            f[u][i] = f[ f[u][i-1] ][i-1]; //动规计算。同样也是一切倍增算法的核心。 
        }
        int k=first[u];
        while(k!=-1){
            v=edges[k].to;
            if(!have[v]) {
                have[v]=1;        
                f[v][0]=u;                 //将要找的下一个点的父节点标为当前处理的节点u。 
                dfs(v,h+1);
            }
            k=next[k];
        }
    }
    int require_LCA(int a,int b){
        int da=height[a],db=height[b];
    //第一步，将a，b两点移到同样的高度，只动高度大的那个点而不动高度小的那个点。 
        if(da!=db) {
            if(da<db){                   //保证a的高度是大于b的高度的。 
                swap(a,b);
                swap(da,db);
            }
            int d=da-db;
            for(int i=0;i<=log2n;i++) 
                if( (1<<i) & d) a=f[a][i]; //这里的位运算可以减少代码量
                                           //考虑到d是一个定值，而（1<<i）在二进制中只有第（i+1）位是1； 
                                           //那么d与（1<<i）如果某一位为1，那么表示可以向上移动， 
                                           //如果此时不移动，那么i增大了后就无法使height[a]==height[b]了 
        }
    //第二步,找到某个位置i，在这个位置时，f[a][i]!=f[b][i],但再向上移动一步，a，b相同了 
    //从log2n开始从大到小枚举i，如果超过了a，b的高度，则令i继续减小
    //如果没有超过a，b的高度，那么就判断移动了后会不会让a==b，
    //是，则i继续减小，否则，令此时的a=f[a][i],b=f[b][i]; 
        if(a==b) return b;
        int i=0;
        for(i=log2n;i>=0;i--) {
            if(height[ f[a][i] ]<0) continue;
            if( f[a][i]==f[b][i] ) continue;
            else a=f[a][i],b=f[b][i];        //顺便一提，在第二步任何地方没有break；
                                           //我就是因为在这里写了一个break，然后找了我两个小时啊。 
        }    
        return f[a][0];
    }
    /////////////////////////////////
    ///据说从主函数开始阅读是个好习惯。 
    int main(){
    //    freopen("in2.txt","r",stdin);
        n=read();m=read();root=read();
        memset(first,-1,sizeof(first));
        memset(next,-1,sizeof(next));
        int s,t;
        int dsd=2*(n-1);
        for(int i=1;i<=dsd;i+=2) {
            s=read();t=read();      //读入优化。 
            edges[i].from=s;
            edges[i].to=t;
            edges[i+1].from=t;
            edges[i+1].to=s;
            next[i]=first[s];
            first[s]=i;
            next[i+1]=first[t];
            first[t]=i+1;
        }
        // 以上是邻接表，在此不再赘述。 
        log2n=log(n)/log(2)+1;        //C++计算log是自然对数，我们要用的以2为底的对数，故要除以log(2); 
                                      //对无理数加上1或是0.5是个好习惯，可以减小误差； 
        memset(have,0,sizeof(have));
        memset(height,0,sizeof(height));
        memset(f,-1,sizeof(f));
        have[root]=1;                //fa[][]和height[]要在dfs理进行计算，不然根本找不到某个非根节点的父亲是谁; 
        dfs(root,1);                
        for(int i=1;i<=n;i++){
            for(int j=0;j<=log2n;j++) {
                if(height[i] <=(1<<j) ) break;
            }
        }
        for(int i=0;i<m;i++) {      //应对要求进行求解。 
            s=read();t=read();
            int y=require_LCA(s,t);
            printf("%d\n",y);
        }
        return 0;
    }

  2. 树剖法

    Code
    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
    #include <bits/stdc++.h>
    using namespace std;
    namespace LCA {
        const int N = 5e5 + 10;
        vector<int>g[N];
        int dep[N];
        int fa[N];
        int top[N];
        int son[N];
        int siz[N];
        void dfs1(int u, int fa) {
            siz[u] = 1;
            son[u] = 0;
            LCA::fa[u] = fa;
            dep[u] = dep[fa] + 1;
            for (auto v : g[u]) {
                if (v == fa) continue;
                dfs1(v, u);
                siz[u] += siz[v];
                if (siz[v] > siz[son[u]]) son[u] = v;
            }
        }
        void dfs2(int u, int fa, int top) {
            LCA::top[u] = top;
            if (!son[u]) return;
            dfs2(son[u], u, top);
            for (auto v : g[u]) {
                if (v == fa || v == son[u]) continue;
                dfs2(v, u, v);
            }
        }
        int lca(int x, int y) {
            while (top[x] != top[y]) {
                if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
                else y = fa[top[y]];
            }
            return dep[x] < dep[y] ? x : y;
        }
    }
    int n,m,s;
    int main() {
        cin >> n >> m >> s;
        using namespace LCA;
        for (int i = 1; i <= n - 1; i++) {
            int aa, bb;
            cin >> aa >> bb;
            g[aa].push_back(bb);
            g[bb].push_back(aa);
        }
        dfs1(s,0);
        dfs2(s,0,s);
        while (m--) {
            int x, y;
            cin >> x >> y;
            cout<<lca(x,y)<<endl;
            
        }
    }

缩点

一些有关连通性的基本概念

  • 连通分量
    在一张图中的某一连通子图被称为该图的连通分量。

  • 无向图的连通性

    1. 割点
      即删除此点后会使当前连通分量分为两个或多个。

    2. 割边
      即删除此边后会使当前连通分量分为两个或多个。

    3. 双连通

    • 点双连通
      在一连通图中任选两点，若它们之间存在至少两条点不重复的路径，则称为点双连通，也就是说在点双联通中没有割点。

    • 边双联通
      在一连通图中任选两点，若它们之间存在至少两条边不重复的路径，则称为边双连通，也就是说在边双联通中没有割边。

  • 有向图的连通性

    • 强联通
      在有向图中，若有两点 和 可以互相到达，即 可以到达 ， 也可以到达 ，则称 与 是强联通的，若此图中任意两点都可以互相到达，则称此图为强连通图。

经典算法

  1. Tarjan

    Code
    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
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 100;
    int n, m;
    int val[N];
    vector<int>g[N];
    int scc[N], low[N], num[N], cnt, top, dfn, st[N], sum[N];
    int aa[N], bb[N],ans[N];
    void tar();
    void dfs(int u);
    int dfs2(int u);
    int main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> val[i];
        for (int i = 1; i <= m; i++) {
            int aaa, bbb;
            cin >> aaa >> bbb;
            aa[i] = aaa, bb[i] = bbb;
            g[aaa].push_back(bbb);
        }
        tar();
        for (int i = 1; i <= n; i++) {
            g[i].clear();
        }
        for (int i = 1; i <= m; i++) {
            if (scc[aa[i]] != scc[bb[i]]) {
                g[scc[aa[i]]].push_back(scc[bb[i]]);
            }
        }
        int anss=0;
        for(int i=1;i<=n;i++)
            {
                if(!ans[i])
                {
                    anss=max(dfs2(i),anss);
                }
            }
        cout<<anss<<endl;
        return 0;
    }
    void tar() {
        for (int i = 1; i <= n; i++) {
            if (!num[i]) dfs(i);
        }
    }
    void dfs(int u) {
        num[u] = low[u] = ++dfn;
        st[top++] = u;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (!num[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (!scc[v]) {
                low[u] = min(low[u], num[v]);
            }
        }
        if (num[u] == low[u]) {
            cnt++;
            while (1) {
                int v = st[--top];
                scc[v] = cnt;
                sum[cnt] += val[v];
                if (u == v)break;
            }
        }
        return;
    }
    int dfs2(int x)
    {
        if(ans[x]) return ans[x];
        ans[x]=sum[x];
        int w=0;
        for(int i=0;i<g[x].size();i++)
        {
            int v=g[x][i];
            w=max(w,dfs2(v));
        }
        ans[x]+=w;
        return ans[x];
    }

  2. Kosaraju
    一个不太常用的算法，可以自行了解。

欧拉路

直接贺的OI-WIKI。

定义

  • 欧拉回路：通过图中每条边恰好一次的回路
  • 欧拉通路：通过图中每条边恰好一次的通路
  • 欧拉图：具有欧拉回路的图
  • 半欧拉图：具有欧拉通路但不具有欧拉回路的图

性质

欧拉图中所有顶点的度数都是偶数。

若 是欧拉图，则它为若干个环的并，且每条边被包含在奇数个环内。

判别法

  1. 无向图是欧拉图当且仅当：
  • 非零度顶点是连通的
  • 顶点的度数都是偶数
  1. 无向图是半欧拉图当且仅当：
  • 非零度顶点是连通的
  • 恰有 个奇度顶点
  1. 有向图是欧拉图当且仅当：
  • 非零度顶点是强连通的
  • 每个顶点的入度和出度相等
  1. 有向图是半欧拉图当且仅当：
  • 非零度顶点是弱连通的
  • 至多一个顶点的出度与入度之差为
  • 至多一个顶点的入度与出度之差为
  • 其他顶点的入度和出度相等

无向图欧拉路求解算法

Code
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
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int du[N];
int m;
int n;
int st;
vector<int>g[N];
map<pair<int, int>, int>mp;
int tmp[N];
int ans[N];
int top;
void find(int u) {
    while (1) {
        int siz = g[u].size();
        while (tmp[u] < siz && !mp[ {u, g[u][tmp[u]]}])++tmp[u];
        if (tmp[u] >= siz) break;
        int v = g[u][tmp[u]];
        mp[ {u, v}]--;
        mp[ {v, u}]--;
        ++tmp[u];
        find(v);
    }
    ans[++top] = u;
}
int main() {
    cin >> m;
    st = n = 510;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        du[u]++, du[v]++;
        st = min(st, min(u, v));
        mp[ {u, v}]++, mp[ {v, u}]++;
    }
    for (int i = 1; i <= n; i++) {
        if (du[i] & 1) {
            st = i;
            break;
        }
    }
    for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
    find(st);
    while (top)printf("%d\n", ans[top--]);
}

基环树

基本概念

基环树就是有一个环的树，若将该环断开任意一条边，则会形成一棵树，若全部断开则会形成森林。

  • 内向树
    就是每个点有且仅有一条出边内向树

  • 外向树
    就是每个点有且仅有一条入边外向树

解题思路

绝大部分基环树的题基本都是用拆环来解决的，可以说处理好环就处理好了基环树。

  • 例题 P4381 [IOI2008] Island

    Code
    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>
    using namespace std;
    #define int long long
    const int N = 7002100;
    int n;
    int head[N];
    int cnt = 1;
    struct edge {
        int u, v, val, nxt;
    } e[N << 1];
    int f[N];
    short vis[N];
    bool vis2[N];
    bool vise[N << 1];
    int sum[N << 1];
    int r[N];
    int tot;
    int pre[N];
    int deq[N << 1],frt,tal;
    bool findr(int u) {
        if (vis[u] == 1) {
            vis[u] = 2;
            vis2[u] = 1;
            r[++tot]=u;
            return 1;
        }
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nxt) {
            if (vise[i]) continue;
            vise[i] = vise[i ^ 1] = 1;
            if (findr(e[i].v)) {
                pre[e[i].v] = i;
                if (vis[u] != 2) {
                    r[++tot]=u;
                    vis2[u] = 1;
                    return 1;
                } else return 0;
            }
        }
        return 0;
    }
    int ans;
    void dp(int u) {
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            int val = e[i].val;
            if (vis2[v]) continue;
            vis2[v]=1;
            dp(v);
            ans = max(ans, f[u] + f[v] + val);
            f[u] = max(f[u], f[v] + val);
        }
    }
    void ADD(int u, int v, int val) {
        ++cnt;
        e[cnt].u = u;
        e[cnt].v=v;
        e[cnt].val=val;
        e[cnt].nxt=head[u];
        head[u] = cnt;
    }
    void add_edge(int u, int v, int val) {
        ADD(u, v, val);
        ADD(v, u, val);
    }
    signed main() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            int v, val;
            cin >> v >> val;
            add_edge(i, v, val);
        }
        int res = 0;
        for(int i=1;i<=n;i++) {
            if(vis2[i]) continue;
            ans = 0;tot = 0;
            frt = 0;tal = -1;
            findr(i);
            for (int i = 1;i <= tot;i ++){
                dp(r[i]);r[i + tot] = r[i];
            }
            for (int i = 1;i <= tot * 2;i ++)
                sum[i] = sum[i - 1] + e[pre[r[i]]].val;
            for (int i = 1;i <= tot * 2;i ++){
                while (frt <= tal && i - deq[frt] + 1 > tot) frt ++;
                if (frt <= tal) ans = max(ans,f[r[deq[frt]]] + f[r[i]] + sum[i - 1] - sum[deq[frt] - 1]);
                while (frt <= tal &&  f[r[deq[tal]]] - sum[deq[tal] - 1] <= f[r[i]] - sum[i - 1])
                    tal --;
                deq[++ tal] = i;
            }
            res+=ans;
        }
        cout<<res;
    }

  • 例题 P3533 [POI2012] RAN-Rendezvous

    Code
    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
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int n, q;
    const int N = 5e5 + 10;
    vector<int>g[N];
    int son[N], dep[N], fa[N], top[N], siz[N], num[N], dfn;
    int vis[N];
    int scc[N];
    int isr[N];
    int in[N];
    int tot;
    stack<int>st;
    int len[N];
    void doit(int u, int id, int az) {
        if (isr[u])return;
        vis[u] = id;
        len[id]++;
        isr[u] = az;
        doit(fa[u], id, az + 1);
    }
    void dfs(int u) {
        siz[u] = 1;
        for (auto v : g[u]) {
            if (v == fa[u] || in[v]) continue;
            dep[v] = dep[u] + 1;
            scc[v] = scc[u];
            dfs(v);
            siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    void dfs(int u, int top) {
        ::top[u] = top;
        if (!son[u]) return;
        dfs(son[u], top);
        for (auto v : g[u]) {
            if (v == fa[u] || in[v] || v == son[u]) continue;
            dfs(v, v);
        }
    }
    int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
            else y = fa[top[y]];
        }
        return dep[x] < dep[y] ? x : y;
    }
    bool check(int a, int b, int c, int d) {
        if (max(a, b) != max(c, d))return max(a, b) < max(c, d);
        if (min(a, b) != min(c, d))return min(a, b) < min(c, d);
        return a >= b;
    }
    signed main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> q;
        for (int i = 1; i <= n; i++) {
            int u;
            cin >> u;
            fa[i] = u;
            g[u].push_back(i);
            in[u]++;
        }
        queue<int>Q;
        for (int i = 1; i <= n; i++) if (!in[i]) Q.push(i);
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            int v = fa[u];
            in[v]--;
            if (!in[v]) Q.push(v);
        }
        for (int i = 1; i <= n; i++) {
            if (in[i]) {
                scc[i] = i;
                dfs(i);
                dfs(i, 0);
                if (!isr[i])doit(i, ++tot, 1);
                fa[i] = 0;
            }
        }
        while (q--) {
            int a, b;
            cin >> a >> b;
            if (vis[scc[a]] != vis[scc[b]]) cout << -1 << ' ' << -1 << endl;
            else if (scc[a] == scc[b]) {
                int lca =::lca(a, b);
                cout << dep[a] - dep[lca] << ' ' << dep[b] - dep[lca] << endl;
            } else {
                int t1 = scc[a], t2 = scc[b];
                int ans1 = dep[a] + (isr[t2] - isr[t1] + len[vis[t1]]) % len[vis[t1]], ans2 = dep[b] + (isr[t1] - isr[t2] + len[vis[t1]]) % len[vis[t1]];
                if (check(dep[a], ans2, ans1, dep[b]))cout << dep[a] << ' ' << ans2 << endl;
                else cout << ans1 << ' ' << dep[b] << endl;
            }
        }
    }

网络流

因为不是 考点所以只提一嘴。

安利一下自己的文章网络流

解题思路

主要就是找到约束条件，在约束条件的基础上建图。

  • 例题 P3973 [TJOI2015] 线性代数
    Code
    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
    #include<bits/stdc++.h>
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int N = 251000;
    const int M = 5e6 + 10;
    int n;
    int b[600][600];
    int c[600];
    int cnt = 1;
    int head[N];
    struct Edge {
        int u, v, c, nxt;
        Edge(int u = 0, int v = 0, int c = 0, int nxt = 0):
            u(u), v(v), c(c), nxt(nxt) {}
    } e[M];
    void ADD(int u, int v, int c) {
        cnt++;
        e[cnt] = Edge(u, v, c, head[u]);
        head[u] = cnt;
    }
    void add_edge(int u, int v, int c) {
        ADD(u, v, c);
        ADD(v, u, 0);
    }
    int dep[N];
    int now[N];
    int s, t;
    bool bfs() {
        memset(dep, 0, sizeof dep);
        queue<int> q;
        dep[s] = 1;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            now[u]=head[u];
            for (int i = head[u]; i; i = e[i].nxt) {
                int v = e[i].v;
                int c = e[i].c;
                if (dep[v] || !c) continue;
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
        return dep[t];
    }
    int dfs(int u,int t,int flow){
        if(u==t) return flow;
        int nowflow=0;
        for(int i=now[u];i&&nowflow<flow;i=e[i].nxt){
            now[u]=i;
            int v=e[i].v;
            int c=e[i].c;
            if(dep[v]!=dep[u]+1||!c) continue;
            int ff=dfs(v,t,min(c,flow-nowflow));
            if(ff) e[i].c-=ff,e[i^1].c+=ff,nowflow+=ff;
            else dep[v]=inf;
        }
        return nowflow;
    }
    int mxflow(){
        int ans=0;
        while(bfs()){
            int nowflow;
            while((nowflow=dfs(s,t,inf))) ans+=nowflow;
        }
        return ans;
    }
    int loc[600][600];
    int main() {
        cin >> n;
        int sum = 0;
        int cc=0;
        s=n*n+n+1;
        t=n*n+n+2;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                cin >> b[i][j];
                sum += b[i][j];
                loc[i][j]=++cc;
                add_edge(s,loc[i][j],b[i][j]);
            }
        for (int i = 1; i <= n; i++) cin >> c[i];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                add_edge(loc[i][j],n*n+i,inf);
                add_edge(loc[i][j],n*n+j,inf);
            }
        for(int i=1;i<=n;i++) add_edge(n*n+i,t,c[i]);
        cout<<sum-mxflow();
    }

建图思想

同余最短路

问题特征
  1. 给 个可以重复利用的整数，要求求出这 个数能拼凑出来多少其他整数。
  2. 给 个整数，求出这 个整数不能拼凑出来的最小/最大整数。
  3. 至少要拼几次才能拼出模 余 的数。

解题思路

我们可以把“拼数”的操作抽象成一个图，我们可以发现 的结构很像最短路中的 ，因此我们可以以此来建图。

  • 例题 P3403 跳楼机

    Code
    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
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e5+100;
    const int inf=0x3f3f3f3f;
    int h,x,y,z;
    vector<pair<int ,int>>g[N];
    int dis[N];
    queue<int>q;
    bool vis[N];
    void add_edge(int aa,int bb,int cc)
    {
        g[aa].push_back({bb,cc});
    }
    void spfa()
    {
        memset(dis,inf,sizeof(dis));
        dis[0]=1;
        vis[0]=1;
        q.push(0);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=0;i<g[u].size();i++)
            {
                int v=g[u][i].first;
                int w=g[u][i].second;
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    if(!vis[v])
                    {
                        q.push(v);
                        vis[v]=1;
                    }
                }
            }
        }
    }
    int ans=0;
    signed main()
    {
        scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
        for(int i=0;i<x;i++)
        {
            add_edge(i,(i+y)%x,y);
            add_edge(i,(i+z)%x,z);
        }
        spfa();
        for(int i=0;i<x;i++)
        {
            if(h>=dis[i]) ans+=(h-dis[i])/x+1;
        }
        printf("%lld",ans);
        return 0;
    }

  • P2371 [国家集训队] 墨墨的等式

    Code
    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 int long long
    const int N=1e3;
    const int M=10e5+10;
    const int inf=1e12;
    int n,l,r;
    int a[N];
    int cnt;
    int mn=1e12;
    vector<pair<int,int>>g[M];
    int dis[M];
    int vis[M];
    void add_edge(int u,int v,int val)
    {
        g[u].push_back({v,val});
    }
    void spfa(int s)
    {
        for(int i=0;i<mn;i++) dis[i]=inf+10;
        dis[s]=0;
        queue<int>q;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=0;i<g[u].size();i++)
            {
                int v=g[u][i].first;
                int w=g[u][i].second;
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    if(!vis[v])
                    {
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
    }
    inline int query(int x) {
        int res = 0;
        for (int i = 0; i < mn; ++i)
            if (dis[i] <= x)
                res += (x - dis[i]) / mn + 1;
        return res;
    }
    signed main()
    {
        cin>>n>>l>>r;
        for (int x, i = 1; i <= n; ++i) {
            cin>>x;
            if (x) {
                a[++cnt] = x;
                mn = min(mn, x);
            }
        }
        n=cnt;
        for (int i = 0; i < mn; ++i)
            for (int j = 1; j <= n; ++j)
                if (a[j] != mn)
                    add_edge(i, (i + a[j]) % mn, a[j]);
        spfa(0);
        int ans1=0,ans2=0;
        ans1=query(l-1),ans2=query(r);
        cout<<ans2-ans1;
    }

分层图

分层图主要用在一些改动图或者受到时间限制的问题中，比较好想。

  • 例题 Grass Cownoisseur G
    Code
    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
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    #include <bits/stdc++.h>
    const int N = 1e6 + 10;
    using namespace std;
    void start() {
        cin.tie(nullptr);
        cout.tie(nullptr);
    }
    int n, m;
    int aa[N],bb[N];
    vector<int>g[N],gg[N],ug[N];
    int val[N], sum[N], low[N], scc[N], num[N], cnt, top, st[N], dfn;
    void dfs(int u) {
        st[top++] = u;
        num[u] = low[u] = ++dfn;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (!num[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            }
            if (!scc[v]) {
                low[u] = min(low[u], num[v]);
            }
        }
        if (num[u] == low[u]) {
            cnt++;
            while (1) {
                int v = st[--top];
                scc[v] = cnt;
                sum[scc[v]] += val[v];
                if (u == v)break;
            }
        }
        return;
    }
    void tar()
    {
        for(int i=1;i<=n;i++)
        {
            if(!num[i])
            {
                dfs(i);
            }
        }
        return;
    }
    void make_map()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<g[i].size();j++)
            {
                int u=scc[i],v=scc[g[i][j]];
                if(u==v)continue;
                gg[u].push_back(v);
                ug[v].push_back(u);
            }
        }
    }
    int dis1[N];
    int dis2[N];
    bool vis1[N];
    bool vis2[N];
    bool vis[N];
    void spfa1(int st)
    {
        queue<int>q;
        q.push(st);
        dis1[st]=sum[st];
        vis1[st]=1;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            vis1[u]=0;
            for(int i=0;i<gg[u].size();i++)
            {
                int v=gg[u][i];
                if(dis1[v]<dis1[u]+sum[v])
                {
                    dis1[v]=dis1[u]+sum[v];
                    //cout<<dis1[v]<<endl;
                    vis1[v]=1;
                    q.push(v);
                }
            }
            vis[u]=1;
        }
    }
    void spfa2(int st)
    {
        queue<int>q;
        q.push(st);
        dis2[st]=sum[st];
        vis2[st]=1;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            vis2[u]=0;
            for(int i=0;i<ug[u].size();i++)
            {
                int v=ug[u][i];
                if(dis2[v]<dis2[u]+sum[v])
                {
                    
                    dis2[v]=dis2[u]+sum[v];
                    //cout<<dis2[v]<<endl;
                    vis2[v]=1;
                    q.push(v);
                }
            }
            vis[u]=1;
        }
    }
    int main() {
        cin.tie(nullptr);
        cout.tie(nullptr);
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            cin>>aa[i]>>bb[i];
            val[aa[i]] = 1;
            val[bb[i]] = 1;
            g[aa[i]].push_back(bb[i]);
        }
        tar();
        make_map();
        int st=scc[1];
        spfa1(st);
        spfa2(st);
        int ans=sum[st];
        for(int ll=1;ll<=n;ll++)
        {
            int u=scc[ll];
            if(dis1[u]&&vis[u])
            {
                vis[u]=0;
                for(int i=0;i<ug[u].size();i++)
                {
                    int v=ug[u][i];
                    if(dis2[v])
                    {
                        ans=max(ans,dis1[u]+dis2[v]-sum[st]);
                    }
                }
            }
        }
        cout<<ans;
        return 0;
    }

差分约束

模拟赛T2没做出来，真的裂开。
问题特征

给定 个变量 以及 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 。求出一组解 ，使得所有的约束条件得到满足，否则判断出无解。

那么很明显这是一个简单的线性规划问题，那么首先我们建立一下单纯型模型（误）。

想看线性规划解法的可以去看我的线性规划入门博客

解题思路

我们先从一个不等式入手

再看看最短路的三角不等式是什么

这两个不等式很明显可以互相转化，如下。

这其实就是差分约束的本质。

  • 例题 P1993 小 K 的农场
    Code
    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
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N = 1e4 + 10;
    vector<pair<int, int>>g[N];
    int cnt[N];
    int n, m;
    int dis[N];
    bool vis[N];
    bool spfa() {
        memset(dis, 0x3f3f3f3f, sizeof dis);
        queue<int>q;
        q.push(n+1);
        dis[n+1] = 0;
        vis[n+1] = 1;
        cnt[n+1]++;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for (int i = 0; i < g[u].size(); i++) {
                int v = g[u][i].first;
                int val = g[u][i].second;
                if (dis[v] > dis[u] + val) {
                    dis[v] = dis[u] + val;
                    if (!vis[v]) {
                        q.push(v), vis[v] = 1;
                        cnt[v]++;
                        if(cnt[v]>n) return 0;
                    }
                }
            }
        }
        return 1;
    }
    signed main() {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            int opt;
            int a, b;
            cin >> opt >> a >> b;
            if (opt == 1) {
                int c;
                cin >> c;
                g[a].push_back({b, -c});
            } else if (opt == 2) {
                int c;
                cin >> c;
                g[b].push_back({a, c});
            } else {
                g[a].push_back({b, 0});
                g[b].push_back({a, 0});
            }
        }
        for(int i=1;i<=n;i++) g[n+1].push_back({i,0});
        if (spfa())puts("Yes");
        else puts("No");
    }

2-SAT

问题特征

给定 个集合 ，表示 与 有某种关系（不能同时选/必须同时选/任意选/其中一个必选）。然后从每个集合选择一个元素，判断能否选 个两两不矛盾的元素。

我们可以令一条有向边 的意义为选了 元素就必须选 元素，用 表示 的反面，下面考虑4中情况：

  • 不能同时选：选 就必须选 ，选 就必须选 ，即 。
  • 必须同时选：选 就必须选 ，选 就必须选 ，即 。
  • 任意选（至少一个）：选 就必须选 ，选 就必须选 ，选 就必须选 ，选 就必须选 ，即 。
  • 必选：直接 ，必然选 。

接下来我们只需要判断 与 是否在一个强连通分量上即可，我们可以使用Tarjan算法。

Code
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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, m;
int dfn, top, cnt, scc[N], num[N], low[N], st[N];
vector<int> g[N];
void tar();
void dfs(int u);
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, a, y, b;
        cin >> x >> a >> y >> b;
        g[x + ((a^1) * (n))].push_back(y + (n * (b )));
        g[y + ((b^1) * n)].push_back(x + (n * (a )));
    }
    tar();
    for (int i = 1; i <= n; i++)
    {
        if (scc[i] == scc[i + n])
        {
            puts("IMPOSSIBLE");
            return 0;
        }
    }
    puts("POSSIBLE");
    for (int i = 1; i <= n; i++)
    {
        if (scc[i] > scc[i + n])
            cout << 1 << " ";
        else
            cout << 0 << " ";
    }
}

void dfs(int u)
{
    num[u] = low[u] = ++dfn;
    st[top++] = u;
    for (int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        if (!num[v])
        {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (!scc[v])
        {
            low[u] = min(low[u], num[v]);
        }
    }
    if (num[u] == low[u])
    {
        cnt++;
        while (1)
        {
            int v = st[--top];
            scc[v] = cnt;
            if (v == u)
                break;
        }
    }
}
void tar()
{
    for (int i = 1; i <= n * 2; i++)
        if (!num[i])
            dfs(i);
}

数据结构优化建图

如果某道题要求区间建边，那么大概率就是数据结构优化建图了。

例题：

前缀优化建图

问题特征
  1. 从 向区间 以外的点连长度为 的边。
  2. 从区间 以外的点向 连长度为 的边。
  3. 从区间 以外的点向 以外的点连长度为 的边。

这种问题也可以用线段树优化解决，但是线段树比较繁琐，根据问题特征，我们其实可以用一种更加简洁的方式————前缀和，来解决这类问题。

我们可以我们可以设置前缀数组 ，令其连向 与 ；设置后缀数组 ，令其连向 与 。

对于操作 ，我们只需要把 连向 和 即可。其余两个操作同理。

例题：

一些奇奇怪怪的建图

例题：

参考资料