§ 题意简述

给定一张有向图，边有边权。每次经过一条边获得边权并将边权乘一个常数。求能获得的最大权值。

§ 题解

其他题解都是Tarjan。这个时候怎么能不上简单好背的Kosaraju呢！

思路很明确，找到图中的环然后榨干这个环的边。然后缩点，加上缩点后的权值。然后跑一个dfs即可。

具体来说就是就是如果每条边不在同一个SCC里面，就两个SCC连边。

如果在一个SCC里面，就把这个SCC里面所有边榨干后的权值和表示为点权。

最后预处理一下每条边被榨干后的权值和即可。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>

using namespace std;

const int MAXN = 8e5 + 5;
vector < int > classic_graph[MAXN];
vector < int > inverse_graph[MAXN];
int n, m, head[MAXN], to[MAXN << 1], val[MAXN << 1], dis[MAXN];
int tot, nxt[MAXN << 1], prepare[MAXN], rnk[MAXN], rec[MAXN];
int inv, S, sum_val[MAXN];
struct EdgeNode {
	int from;
	int to, val;
} cass[MAXN];

void make_edge(int x, int y, int z) {
	to[++tot] = y, val[tot] = z;
	nxt[tot] = head[x], head[x] = tot;
}

void to_init() {
	memset(rec, (inv = 0), sizeof rec);
}

void positive(int x) {
	rec[x] = 1;
	for (auto y : classic_graph[x]) if (!rec[y]) positive(y);
	rnk[++inv] = x;
}

void negative(int x) {
	rec[x] = inv;
	for (auto y : inverse_graph[x]) if (!rec[y]) negative(y);
}

void dfs(int x) {
	if (!dis[x]) {
		dis[x] = sum_val[x];
		int res = 0;
		for (int i = head[x]; i; i = nxt[i])
			dfs(to[i]), res = max(res, dis[to[i]] + val[i]);
		dis[x] += res;
	}
}

void kosaraju() {
	to_init();
	for (int i = 1; i <= n; ++i) if (!rec[i]) positive(i);
	to_init();
	for (int i = n; i >= 1; --i) if (!rec[rnk[i]]) inv++, negative(rnk[i]);
}

void preparing() {
	scanf("%d %d", &n, &m);
	for (int i = 0, x, y, z; i < m; ++i) {
		double delta;
		scanf("%d %d %d %lf", &x, &y, &z, &delta);
		cass[i + 1] = EdgeNode{x, y, z};
		classic_graph[x].push_back(y);
		inverse_graph[y].push_back(x);
		while (z) prepare[i + 1] += z, z = floor(z * delta);
	}
	scanf("%d", &S);
}

void get_answer() {
	kosaraju();
	for (int i = 1; i <= m; ++i)
		if (rec[cass[i].from] == rec[cass[i].to]) sum_val[rec[cass[i].from]] += prepare[i];
		else make_edge(rec[cass[i].from], rec[cass[i].to], cass[i].val);
	dfs(rec[S]);
	printf("%d\n", dis[rec[S]]);
}

signed main() {
	preparing();
	get_answer();
	return 0;
}