玄关
  • 板块P2656 采蘑菇
  • 楼主文锡
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/19 12:54
  • 上次更新2024/9/19 18:43:00
查看原帖
玄关
941628
文锡楼主2024/9/19 12:54
#include<bits/stdc++.h> 
using namespace std;
const int maxn=8e4+10;
const int maxm=4e5+10;
long long n, m;
long long S;
long long head[maxn], nxt[maxm], to[maxm], val[maxm], coe[maxm], tot;
long long dfn[maxn], low[maxn], st[maxn], ins[maxn], bel[maxn], top, idx;
long long vt[maxn], ind[maxn], dp[maxn];
queue<int> que;
void add(int b, int e, int v, int c){
	nxt[++tot]=head[b];
	to[head[b]=tot]=e;
	val[tot]=v;
	coe[tot]=c;
}
void tarjan(int u){
	static int t0t;
	dfn[u]=low[u]=++t0t;
	ins[st[++top]=u]=true;
	for(int i=head[u];i;i=nxt[i])
		if(!dfn[to[i]]){
			tarjan(to[i]);
			low[u]=min(low[u],low[to[i]]);
		}else if(ins[to[i]])
			low[u]=min(low[u],dfn[to[i]]);
	if(low[u]==dfn[u]){
		int v;
		idx++;
		do{
			ins[v=st[top--]]=false;
			bel[v]=idx;
		}while(v!=u);
	}
}
int main(){
	cin>>n>>m;
	int u, v, w;
	for(int i=1;i<=m;++i){
		double _c;
		cin>>u>>v>>w>>_c;
		int c=round(_c*10);
		add(u,v,w,c);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]) tarjan(i);
	static int th[maxn];
	memcpy(th,head,(n+1)<<2);
	memset(head,0,(n+1)<<2);
	for(int u=1;u<=n;++u)
		for(int i=th[u];i;i=nxt[i]){
			int v=to[i];
			if(bel[u]==bel[v]){
				int t=val[i];
				while(t){
					vt[bel[u]]+=t;
					t=t*coe[i]/10;
				}
			}else{
				add(bel[v],bel[u],val[i],0);
				ind[bel[u]]++;
			}
		}
	for(int i=1;i<=idx;++i)
		if(!ind[i]) que.push(i);
	while(!que.empty()){
		int t=que.front();
		que.pop();
		dp[t]+=vt[t];
		for(int i=head[t];i;i=nxt[i]){
			dp[to[i]]=max(dp[to[i]],dp[t]+val[i]);
			if(!--ind[to[i]]) que.push(to[i]);
		}
	}
	cin>>S;
	cout<<dp[bel[S]]<<endl;
	return 0;
}
2024/9/19 12:54
加载中...