题目链接：https://www.luogu.org/problemnew/show/P4742
题目大意：给一张有向图, 每个点都有点权,第一次经过该点时,该点的点权有贡献，求这张图上一条路径（终点随意）的贡献最大并且得到该路径上一个最大点权。
思路：
1.值得注意的是,这里并不是求最长路,也就是并不是求最多的点组成的路径,点可以少,但是必须点权和最大。
2.因为需要得到最大点权和以及最大点权,终点又不定,所以我们需要遍历图中每个点,来得到起点到该点的点权和以及路径上的最大点权。
3.先用tarjan进行缩点处理, 若不这样直接遍历原图非常耗时。缩点的‘点’中需要记录的信息是每个连通分量中点的权值和以及最大的点权。
4.还需要选择一个合理的遍历新图的方式, 那么选用 拓扑排序 ,（拓扑排序只有在设置汇点跳出的情况下得到的路径才不唯一，否则会根据点边关系遍历图中的每个点）
代码：
#include<stdio.h>
#include<string.h>
#include<stack>
#include<queue>
#include<algorithm>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
typedef long long ll; int n, m, in[maxn];
int arr[maxn], max_node[maxn], sum_color[maxn];
int cnt, new_cnt, head[maxn], new_head[maxn];
int dfn[maxn], low[maxn], vis[maxn], belong[maxn], deep, color;
int dis[maxn], d_node[maxn];//dis代表从起点到该点的点权和,d_node代表起点到该点的点权最大值
stack<int>S;
queue<int>Q; struct Edge
{
int to, next;
}edge[maxm], new_edge[maxm]; void add(int a, int b)
{
edge[++ cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt;
} void new_add(int a, int b)
{
new_edge[++ new_cnt].to = b;
new_edge[new_cnt].next = new_head[a];
new_head[a] = new_cnt;
} void tarjan(int now)
{
dfn[now] = low[now] = ++ deep;
vis[now] = ;
S.push(now);
for(int i = head[now]; i != -; i = edge[i].next)
{
int to = edge[i].to;
if(!dfn[to])
{
tarjan(to);
low[now] = min(low[now], low[to]);
}
else if(vis[to])
low[now] = min(low[now], dfn[to]);
}
if(low[now] == dfn[now])
{
color ++;
while()
{
int temp = S.top();
S.pop();
vis[temp] = ;
belong[temp] = color;
max_node[color] = max(max_node[color], arr[temp]); //存每个强连通分量里亮度最大的点的值
sum_color[color] += arr[temp];//存每个强连通分量里的亮度和
if(temp == now)
break;
}
}
} void topu_sort()
{
// mem(dis, -inf);
while(!Q.empty())
Q.pop();
for(int i = ; i <= color; i ++)//topu_sort将入度为0的入队 ,并初始化d_node,每个分量的最大亮度
{
dis[i] = sum_color[i]; //初始化dis, d_node
d_node[i] = max_node[i];
if(!in[i])
Q.push(i);
}
while(!Q.empty())
{
int temp = Q.front();
Q.pop();
for(int i = new_head[temp]; i != -; i = new_edge[i].next)
{
int to = new_edge[i].to;
in[to] --;
if(!in[to])
Q.push(to);
if(dis[to] <= dis[temp] + sum_color[to])//选择新入的点,那么d_node就要与新入的缩点比较了
{
dis[to] = dis[temp] + sum_color[to];
d_node[to] = max(d_node[temp], max_node[to]);
}
/*
else if(dis[to] == dis[temp] + sum_color[to])
d_node[to] = max(d_node[temp], max_node[to]);
*/
}
}
int sum = -;
int maxx;
for(int i = ; i <= color; i ++)
{
if(dis[i] > sum)
{
sum = dis[i];
maxx = d_node[i];
}
}
printf("%d %d\n", sum, maxx);
} int main()
{
cnt = new_cnt = deep = color = ;
mem(head, -), mem(new_head, -), mem(in, );
mem(vis, ), mem(dfn, ), mem(low, );
mem(max_node, -inf), mem(sum_color, );
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i ++)
scanf("%d", &arr[i]); //存每个点的光亮值
for(int i = ; i <= m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
for(int i = ; i <= n; i ++)
if(!dfn[i])
tarjan(i);
for(int i = ; i <= n; i ++)
{
for(int j = head[i]; j != -; j = edge[j].next)
{
int to = edge[j].to;
int x = belong[i], y = belong[to]; //将分量连边 缩点 注意是分量 belong
if(x != y)
{
new_add(x, y);
in[y] ++;
}
}
}
topu_sort();
return ;
}
