小萌新 玄关 30pts 球求拉
查看原帖
小萌新 玄关 30pts 球求拉
1046223
a_blue_fool楼主2024/12/18 14:13
#include <iostream>
#include <cstdio>
#include <vector>

#define N 80005
#define M 200005
#define pb push_back

using namespace std;

struct link{
	int v, w;
};

int n, m, s;
int u[M], v[M], a[M], w[M], k[M];
int cnt, tot, top;
int dfn[N], low[N], tag[N], sta[N], val[N];
bool vis[N];
int dp[N];
vector <int> g1[N];
vector <link> g2[N];

int f(int a, int k) {
	int ans = 0;
	
	while(a > 0) {
		ans += a;
		a *= k / 10;
	}
	
	return ans;
}

void tarjan(int u) {
	dfn[u] = low[u] = ++cnt;
	vis[u] = true;
	sta[++top] = u;
	
	for (auto v : g1[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (vis[v])
			low[u] = min(low[u], dfn[v]);
	}
	
	if (low[u] == dfn[u]) {
		tot++;
		
		while(sta[top + 1] != u) {
			tag[sta[top]] = tot;
			vis[tag[top]] = false;
			
			top--;
		}
	}
	
	return;
}

void dfs(int u) {
	if (dp[u])
		return;
	
	for (auto i : g2[u]) {
		int v = i.v, w = i.w;
		dfs(v);
		
		dp[u] = max(dp[u], dp[v] + w); 
	}
	
	dp[u] += val[u];
	
	return;
}

int main() {
	freopen("P2656_4.in", "r", stdin);
	
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		float x;
		
		scanf("%d%d%d%f", &u[i], &v[i], &a[i], &x);
		k[i] = x * 10;
		
		w[i] = f(a[i], k[i]);
		g1[u[i]].pb(v[i]);
	}
	scanf("%d", &s);
	
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i);
	
	for (int i = 1; i <= m; i++) {
		if (tag[u[i]] == tag[v[i]]) {
			val[tag[u[i]]] += w[i];
		}
		else { //tag[u[i]] != tag[v[i]]
			g2[tag[u[i]]].pb({tag[v[i]], a[i]});
		}
	}
	
	dfs(tag[s]);
	
	printf("%d", dp[tag[s]]);
	return 0;
}
2024/12/18 14:13
加载中...