0分求调
  • 板块P2656 采蘑菇
  • 楼主zrt090604
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/27 11:32
  • 上次更新2024/11/27 15:40:20
查看原帖
0分求调
459188
zrt090604楼主2024/11/27 11:32
#include<bits/stdc++.h>
using namespace std;
const int N = 8e4 + 5, M = 4e5 + 5;
int n, m, s;
bool in[N];
int dfn[N], low[N], t, stk[N], tp, gr[N], scc, sum[N];
int hd[N], cnt, hd2[N], cnt2;
int dis[N], vis[N];
queue<int> q;
struct Node {
	int from, to, nx, w, k;
} e[M], eg[M];
void add(int u, int v, int w, int k) {
	e[++cnt] = {u, v, hd[u], w, k};
	hd[u] = cnt;
}
void add2(int u, int v, int w) {
	eg[++cnt2].to = v;
	eg[cnt2].nx = hd2[u];
	eg[cnt2].w = w;
	hd2[u] = cnt2; 
}
void tarjan(int u) {
	dfn[u] = low[u] = ++t;
	in[u] = true;
	stk[++tp] = u;
	for(int i = hd[u]; i; i = e[i].nx) {
		int v = e[i].to;
		if(!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(in[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]) {
		int y;
		++scc;
		do {
			y = stk[tp];
			--tp;
			gr[y] = scc;
			in[y] = false;
		} while(y != u);
	}
}
void spfa(int s) {
	memset(dis, -1, sizeof dis);
	dis[s] = sum[s];
	q.push(s);
	vis[s] = 1;
	while(!q.empty()) {
		int x = q.front(); q.pop();
		vis[x] = false;
		for(int i = hd2[x]; i; i = eg[i].nx) {
			int y = eg[i].to;
			if(dis[y] < dis[x]+eg[i].w+sum[y]) {
				dis[y] = dis[x]+eg[i].w+sum[y];
				if(!vis[y]) {
					vis[y] = true;
					q.push(y);
				}
			}
		}
	}
}
int main () {
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;++i) {
		int x, y, z;
		double k;
		scanf("%d%d%d%lf", &x, &y, &z, &k);
		add(x, y, z, k*10);
	}
	for(int i = 1;i <= n;++i)
		if(!dfn[i]) tarjan(i);
	for(int i = 1;i <= m;++i) {
		int x = e[i].from, y = e[i].to, z = e[i].w, k = e[i].k;
		if(gr[x] == gr[y]) {
			while(z) {
				sum[gr[x]] += z;
				z = z*k/10;
			}
		}
		else add2(gr[x], gr[y], z);
	}
	scanf("%d", &s);
	s = gr[s];
	spfa(s);
	int ans = 0;
	for(int i = 1;i <= scc;++i)
		ans = max(ans, dis[i]);
	printf("%d", ans);
	return 0;
}
2024/11/27 11:32
加载中...