给出插头Dp的模板代码,并详细解释

插头DP是一种常见的动态规划算法，主要用于求解一些有依赖关系的问题，如图论中的最小路径覆盖、字符串匹配中的最长公共子序列等等。

插头DP的主要思想是将原问题转化为一个有向无环图（DAG）上的最长路径问题，其中每个节点表示原问题中的一个状态，每个边表示从一个状态转移到另一个状态的操作。插头DP的核心是“插头”，即在DAG中插入一些边来保证每个状态只被计算一次。

下面给出插头DP的模板代码，并详细解释每一部分的含义：

const int N = 100010;
int n, m, idx; // idx表示DAG中节点的数量
int h[N], e[N], ne[N], idx; // 邻接表存储DAG
int f[N]; // f[i]表示以i为终点的最长路径
int g[N]; // g[i]表示以i为起点的最长路径
int q[N], d[N]; // q存储拓扑序列，d[i]表示i的入度
bool st[N]; // st[i]表示i是否在拓扑序列中

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void topsort() {
    int hh = 0, tt = -1;

    // 将所有入度为0的点加入队列
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) q[ ++ tt] = i;

    // 拓扑排序
    while (hh <= tt) {
        int t = q[hh ++ ];
        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (-- d[j] == 0) q[ ++ tt] = j;
        }
    }
}

int main() {
    memset(h, -1, sizeof h);

    // 读入图
    scanf("%d%d", &n, &m);
    while (m -- ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b] ++ ;
    }

    // 求出DAG中的拓扑序列
    topsort();

    // 计算每个节点的g数组
    for (int i = 0; i < idx; i ++ ) {
        int j = e[i];
        if (st[j]) g[j] = max(g[j], f[e[i ^ 1]] + 1);
    }

    // 计算每个节点的f数组
    for (int i = n; i; i -- ) {
        int j = q[i];
        for (int k = h[j]; ~k; k = ne[k])
            f[j] = max(f[j], g[e[k]] + 1);
    }

    // 求最长路径
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    printf("%d\n", res);
    return 0;
}

1. 声明变量

const int N = 100010;
int n, m, idx; // idx表示DAG中节点的数量
int h[N], e[N], ne[N], idx; // 邻接表存储DAG
int f[N]; // f[i]表示以i为终点的最长路径
int g[N]; // g[i]表示以i为起点的最长路径
int q[N], d[N]; // q存储拓扑序列，d[i]表示i的入度
bool st[N]; // st[i]表示i是否在拓扑序列中

2. 存储图并求拓扑序列

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void topsort() {
    int hh = 0, tt = -1;

    // 将所有入度为0的点加入队列
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) q[ ++ tt] = i;

    // 拓扑排序
    while (hh <= tt) {
        int t = q[hh ++ ];
        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (-- d[j] == 0) q[ ++ tt] = j;
        }
    }
}

int main() {
    memset(h, -1, sizeof h);

    // 读入图
    scanf("%d%d", &n, &m);
    while (m -- ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b] ++ ;
    }

    // 求出DAG中的拓扑序列
    topsort();
}

首先定义一个add函数，用于存储原图的边，同时记录每个节点的入度。然后定义一个topsort函数，用于求出DAG的拓扑序列。具体实现是通过队列来实现的，首先将所有入度为0的点加入队列，然后依次取出队首节点，并将与之相连的节点的入度减1，若入度减为0，则将该节点加入队列。最终得到的队列即为DAG的拓扑序列。

3. 计算每个节点的g数组

for (int i = 0; i < idx; i ++ ) {
    int j = e[i];
    if (st[j]) g[j] = max(g[j], f[e[i ^ 1]] + 1);
}

对于每个节点j，遍历与之相连的所有入边，对应的起点为e[i ^ 1]（由于存储原图和存储DAG的边是交替存储的，所以需要异或1），若起点在拓扑序列中，则更新g[j]的值。

4. 计算每个节点的f数组

for (int i = n; i; i -- ) {
    int j = q[i];
    for (int k = h[j]; ~k; k = ne[k])
        f[j] = max(f[j], g[e[k]] + 1);
}

对于每个节点j，遍历与之相连的所有出边，对应的终点为e[k]，更新f[j]的值。

5. 求最长路径

int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
printf("%d\n", res);

遍历所有节点，找到以每个节点为终点的最长路径，取最大值即为DAG的最长路径。