题解 P2656 【采蘑菇】
tarjan+topo+DP!!!
此题主要是让我们在缩完点后求一条从起点出发的带点权的最长路，因此我们在tarjan缩完点后直接跑拓扑排序+DP就可以了
首先是简单的tarjan缩点 码风略丑勿喷
void tarjan(int u)
{
dfn[u] = low[u] = ++index;
stack[++top] = u;
instack[u] = true;
for (int e = head[u]; e; e = edge[e].next)
{
int v = edge[e].to;
if (!dfn[v])
{
tarjan(v);
low[u] = std::min(low[u], low[v]);
}
else if (instack[v])
{
low[u] = std::min(low[u], low[v]);
}
}
if (dfn[u] == low[u])
{
++sc;
while(stack[top] != u)
{
scc[stack[top]] = sc;
instack[stack[top]] = false;
top--;
}
scc[u] = sc;
instack[u] = false;
top--;
}
}缩完点后我们可以发现： 因为强连通分量里任意两点均直接或间接连通，所以这两点间连接的路径上的蘑菇我们是可以一直采，采到没有为止的。而对于连接两个强连通分量的边，边上的蘑菇我们是只能采一次的，因为我们从这条边的起点走到终点是无法再走回去的，否则这两个点应属于同一个强连通分量。
所以得出一个显而易见的结论：对于原图中的任意一条边，如果边的起点和终点在同一强连通分量中，边的权值是可以一直取的（每次乘恢复系数），而如果不在同一强连通分量中，则只取一次。
我们可以利用这个结论建一个新图!!!
遍历原图中的每一条边，如果起点终点在同一强连通分量，将边权（一直乘恢复系数直到零）加到强连通分量的点权中，如果不在同一强连通分量，就在强连通分量之间建一条有向边，边权为原边权。
for (int i = 1; i <= m; i++)
{
if (scc[edge[i].start] != scc[edge[i].to])
{
add_edge2(scc[edge[i].start], scc[edge[i].to], edge[i].w);
in[scc[edge[i].to]]++;
}
else
{
while (edge[i].w)
{
val[scc[edge[i].to]] += edge[i].w;
edge[i].w *= edge[i].k;
}
}
}现在新图建好了，那么如何在一个有向无环图中求一条带点权有起点的最长路径呢？
我们可以对新图进行一次拓扑排序，这样可以保证用来更新的点是之前已经被更新过的，但要注意一点细节。
我们设f[i]表示从i号点(强连通分量)到起点的最长路径，由于我们的起点不一定是拓扑排序的起点，也就是说起点的入度不一定为零，我们在初始化的时候，将f数组设一个极小值，将f[s(起点)]设成s的点权就可以了(ps:这里的起点指的是起点所在的强连通分量的编号)。还有一点需要注意的就是，我们要求的是带点权的最长路经，因此在更新的时候直接带着点权更新就好了。最后对f数组求一个最大值，就是我们想要的答案了。
topo + DP
void topo()
{
for (int i = 1; i <= sc; i++)
{
if (!in[i])
q.push(i);
f[i] = -0x7fffffff;
}
f[scc[s]] = val[scc[s]];
while(!q.empty())
{
int u = q.front();
q.pop();
for (int e = head2[u]; e; e = edge2[e].next)
{
int v = edge2[e].to;
f[v] = std::max(f[u] + edge2[e].w + val[v], f[v]);
in[v]--;
if (!in[v])
q.push(v);
}
}
for (int i = 1; i <= sc; i++)
ans = std::max(ans, f[i]);
}下面是完整代码：
sc是强连通分量的数量(编号从1-sc)，scc[i]表示点i在编号为scc[i]的强连通分量中。edge是原图，edge2是新图。
#include <cstdio>
#include <queue>
#include <algorithm>
const int N_MAX = 3000000 + 7;
const int M_MAX = 5000000 + 7;
struct Edge
{
int start, to, w, next;
double k;
} edge[M_MAX], edge2[M_MAX];
int edge_size, head[N_MAX];
void add_edge(int u, int v, int w, double k)
{
edge[++edge_size] = (Edge) {u, v, w, head[u], k};
head[u] = edge_size;
}
int head2[N_MAX], edge_size2;
void add_edge2(int u, int v, int w)
{
edge2[++edge_size2] = (Edge) {u, v, w, head2[u], 0};
head2[u] = edge_size2;
}
int low[N_MAX], dfn[N_MAX], stack[N_MAX], top;
bool instack[N_MAX];
int scc[N_MAX], sc, index;
void tarjan(int u)
{
dfn[u] = low[u] = ++index;
stack[++top] = u;
instack[u] = true;
for (int e = head[u]; e; e = edge[e].next)
{
int v = edge[e].to;
if (!dfn[v])
{
tarjan(v);
low[u] = std::min(low[u], low[v]);
}
else if (instack[v])
{
low[u] = std::min(low[u], low[v]);
}
}
if (dfn[u] == low[u])
{
++sc;
while(stack[top] != u)
{
scc[stack[top]] = sc;
instack[stack[top]] = false;
top--;
}
scc[u] = sc;
instack[u] = false;
top--;
}
}
int f[N_MAX], val[N_MAX], in[N_MAX], ans;
std::queue <int> q;
int s;
void topo()
{
for (int i = 1; i <= sc; i++)
{
if (!in[i])
q.push(i);
f[i] = -0x7fffffff;
}
f[scc[s]] = val[scc[s]];
while(!q.empty())
{
int u = q.front();
q.pop();
for (int e = head2[u]; e; e = edge2[e].next)
{
int v = edge2[e].to;
f[v] = std::max(f[u] + edge2[e].w + val[v], f[v]);
in[v]--;
if (!in[v])
q.push(v);
}
}
for (int i = 1; i <= sc; i++)
ans = std::max(ans, f[i]);
}
int n, m, u, v, w;
double k;
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d %lf", &u, &v, &w, &k);
add_edge(u, v, w, k);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= m; i++)
{
if (scc[edge[i].start] != scc[edge[i].to])
{
add_edge2(scc[edge[i].start], scc[edge[i].to], edge[i].w);
in[scc[edge[i].to]]++;
}
else
{
while (edge[i].w)
{
val[scc[edge[i].to]] += edge[i].w;
edge[i].w *= edge[i].k;
}
}
}
scanf("%d", &s);
topo();
printf("%d\n", ans);
}
虽然不算很长但也写了一百三十行，这也是本蒟蒻的第一篇题解，如果有不懂的地方可以私信我。