2378 字
12 分钟
【题解】P3387 【模板】缩点
题目链接：【模板】缩点
前言
审题
给一张图，找一条路径使点权和最大。
思路
先用tarjan算法求出这张图中所有的强连通分量，将它们缩成一点，建一个缩点后的图。 这次题目让我们求这张图上的一条路径，使经过的点权之和最大。看到“最”，就会想到和最短路有关。但是这题求的是最大的点权之和，就需要考虑把最短路算法魔改一下。
这篇题解使用的是LPFA算法~~（Longest Path Fast Algorithm，发明者：沃·兹基硕德）~~
把SPFA算法的边权改为点权，松弛改为扩张：
if (dis[v] > dis[u] + siz[v]) dis[v] = dis[u] + siz[v];->if (dis[v] < dis[u] + siz[v]) dis[v] = dis[u] + siz[v];整个LPFA的代码如下：
void spfa(int s) { //LPFA开始 queue<int> que; //定义队列que que.push(s); //将s push进队列 dis[s] = siz[s]; //将s出发的最长路的值初始化为它所在连通块的权值之和 used[s] = true; //标记s在队列中 while (!que.empty()) { //当队列不为空（即有值）时循环 int u = que.front(); //把u赋为que的队首元素 que.pop(); //删除que中的第一个元素 used[u] = false; //标记u不在队列中 for (int i = head[u]; ~i; i = edge[i].next) { //循环从u出发的所有边 int v = edge[i].to; //定义点v并把它赋值为这条边的终点 if (dis[v] < dis[u] + siz[v]) { //如果现在的“最长路”没有先走u的长度长 dis[v] = dis[u] + siz[v]; //就对路径进行“扩张”操作 if (!used[v]) { //如果点v不在队列中 used[v] = true; //标记它加入队列 que.push(v); //把它加入队列 } } } } for (int i = 1; i <= sccnt; i++) //循环每一个强连通分量，找dis（最长路）的最大值 ans = max(ans, dis[i]); //如果dis[i]比答案大，就让答案为dis[i]}因为需要求出权值的最大和，所以tarjan函数里面多了这样一句：
siz[sccnt] += val[u];整个tarjan()函数如下
void tarjan(int v) { //Tarjan算法 dfn[v] = low[v] = ++tot; //标记dfn[]访问顺序，还有low[]的初始值 sta.push(v); //让点v进栈 vis[v] = true; //标记这个点被访问过 for (int i = head[v]; ~i; i = edge[i].next) { //一直循环这个点每一个出度，直到-1表示没有了，这也是为什么memset head数组时要赋-1 int u = edge[i].to; //定义u并把它赋成这条边的终点 if (!dfn[u]) { //如果u没有被访问过 tarjan(u); //找下面这个点 low[v] = min(low[v], low[u]); //这个点low[v]的值就是当前low[]的值与找到的u点的low[]值 } else if (vis[u]) //如果u被访问过了，但是还在队列中 low[v] = min(low[v], dfn[u]); //low[v]就取这个点的low值与循环到的点u的dfn[u]的最小值 } if (dfn[v] == low[v]) { //如果发现v这个点的dfn[]和low[]相等，说明这个点是一个强连通分量的“根”。 sccnt++; //scc（Strongly Connected Component）， cnt（count），就是强连通分量的个数 int u; //定义u变量，作为栈顶元素 do { u = sta.top(); //将u赋值为sta栈的栈顶元素 vis[u] = false; //将u弹出 sta.pop(); //同上 color[u] = sccnt; //将u标记为这个强连通分量里的点 siz[sccnt] += val[u]; //这个强连通分量的权值加上u这个点的权值 } while (v != u); //当v == u之后，结束循环 }}为了使每一个点都被访问到，tarjan()的调用在循环中进行：
for (int i = 1; i <= n; i++) //循环每一个点 if (!dfn[i]) tarjan(i); //如果dfn[i]没有值，即这个点被没有访问过，需要访问； //如果dfn[i]已经有一个值，说明这个点被访问过了，不用担心漏了， //同时也为了节省时间，就不访问了。建缩点后的图时，将原来的head[]和edge[]数组清空，循环每一条边，如果它的起点和终点不在一个强连通分量中，则连一条边：
for (int i = 1; i <= m; i++) //循环每一条边 if (color[from[i]] != color[to[i]]) //如果这条边的出发点和终止点不在同一个强连通分量中 add(color[from[i]], color[to[i]]); //就连一条边代码
完整代码如下：
#include <bits/stdc++.h> //万能头文件using namespace std; //名字空间，具体我也不知有啥用，但是有用到了iostream就得加这个，否则就得std::const int maxN = 2e5 + 3; //数组大小
struct Edge { int next, to; //用结构体存邻接表} edge[maxN];int head[maxN], dfn[maxN], low[maxN];int color[maxN], val[maxN], siz[maxN];int from[maxN], to[maxN], dis[maxN];bool vis[maxN], used[maxN];int cnt, tot, sccnt, ans, n, m;stack<int> sta;
//以上定义了一包变量和数组
template<typename Tp> void read(Tp &x) { char c = getchar(); //先输入一个字符 x = 0; //定义x并初始化为0，用来累计输入的数 while (!isdigit(c)) c = getchar(); //如果这个字符不是数字的话，就一直读下一个字符（本题没有负数情况） do { x = x * 10 + (c ^ 48); //先把x×10，然后与c^48相加 //十进制48转换为二进制为110000，而'0'到'9'都是11****，异或会使不同的位为1，相同的位为0 c = getchar(); //读下一个字符 } while (isdigit(c)); //循环条件为读到的为数字，则一直循环到读入的不是数字为止}
void add(int from, int to) { edge[++cnt].next = head[from], edge[cnt].to = to, head[from] = cnt;}
void tarjan(int v) { //Tarjan算法 dfn[v] = low[v] = ++tot; //标记dfn[]访问顺序，还有low[]的初始值 sta.push(v); //让点v进栈 vis[v] = true; //标记这个点被访问过 for (int i = head[v]; ~i; i = edge[i].next) { //一直循环这个点每一个出度，直到-1表示没有了，这也是为什么memset head数组时要赋-1 int u = edge[i].to; //定义u并把它赋成这条边的终点 if (!dfn[u]) { //如果u没有被访问过 tarjan(u); //找下面这个点 low[v] = min(low[v], low[u]); //这个点low[v]的值就是当前low[]的值与找到的u点的low[]值 } else if (vis[u]) //如果u被访问过了，但是还在队列中 low[v] = min(low[v], dfn[u]); //low[v]就取这个点的low值与循环到的点u的dfn[u]的最小值 } if (dfn[v] == low[v]) { //如果发现v这个点的dfn[]和low[]相等，说明这个点是一个强连通分量的“根”。 sccnt++; //scc（Strongly Connected Component）， cnt（count），就是强连通分量的个数 int u; //定义u变量，作为栈顶元素 do { u = sta.top(); //将u赋值为sta栈的栈顶元素 vis[u] = false; //将u弹出 sta.pop(); //同上 color[u] = sccnt; //将u标记为这个强连通分量里的点 siz[sccnt] += val[u]; //这个强连通分量的权值加上u这个点的权值 } while (v != u); //当v == u之后，结束循环 }}void spfa(int s) { //LPFA开始 queue<int> que; //定义队列que que.push(s); //将s push进队列 dis[s] = siz[s]; //将s出发的最长路的值初始化为它所在连通块的权值之和 used[s] = true; //标记s在队列中 while (!que.empty()) { //当队列不为空（即有值）时循环 int u = que.front(); //把u赋为que的队首元素 que.pop(); //删除que中的第一个元素 used[u] = false; //标记u不在队列中 for (int i = head[u]; ~i; i = edge[i].next) { //循环从u出发的所有边 int v = edge[i].to; //定义点v并把它赋值为这条边的终点 if (dis[v] < dis[u] + siz[v]) { //如果现在的“最长路”没有先走u的长度长 dis[v] = dis[u] + siz[v]; //就对路径进行“扩张”操作 if (!used[v]) { //如果点v不在队列中 used[v] = true; //标记它加入队列 que.push(v); //把它加入队列 } } } } for (int i = 1; i <= sccnt; i++) //循环每一个强连通分量，找dis（最长路）的最大值 ans = max(ans, dis[i]); //如果dis[i]比答案大，就让答案为dis[i]}int main() { memset(head, -1, sizeof(head)); //把head[]数组初始化为-1，具体原因见tarjan函数 read(n), read(m); //输入n、m for (int i = 1; i <= n; i++) read(val[i]); //输入每一个点的权值 for (int i = 1; i <= m; i++) { read(from[i]), read(to[i]); //输入每一条边的起点和重点 add(from[i], to[i]); //把起点和终点连一条边 } for (int i = 1; i <= n; i++) //循环每一个点 if (!dfn[i]) tarjan(i); //如果dfn[i]没有值，即这个点被没有访问过，需要访问； //如果dfn[i]已经有一个值，说明这个点被访问过了，不用担心漏了， //同时也为了节省时间，就不访问了。 memset(head, -1, sizeof(head)); //将原来的head[]数组清空，以便重新建图 memset(edge, 0, sizeof(edge)); //将原来的edge[]数组清空，以便重新建图 for (int i = 1; i <= m; i++) //循环每一条边 if (color[from[i]] != color[to[i]]) //如果这条边的出发点和终止点不在同一个强连通分量中 add(color[from[i]], color[to[i]]); //就连一条边 for (int i = 1; i <= sccnt; i++) spfa(i); //循环每一个连通块（单独的一个点也是一个连通块），因为每一个连通块已经缩成一个点，所以就可以当作一个点来对待 printf("%d\n", ans); //输出答案} 【题解】P3387 【模板】缩点
https://xn--24wq0n.top/posts/2021-04-08-题解_p3387_模板_缩点/