30pts求助
  • 板块P2656 采蘑菇
  • 楼主rmzls
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/3/30 16:44
  • 上次更新2023/10/23 20:02:11
查看原帖
30pts求助
261574
rmzls楼主2023/3/30 16:44

30pts,不知道哪里错了

#include<bits/stdc++.h>
#define next nxt
using namespace std;
const int N=8e4+10,M=2e5+10;
double k[M],k2[M];
int val[M],to[M],head[N],next[M];
int val2[M],to2[M],head2[N],next2[M];
int cntt,n,m,v[N],q,dfn[N],low[N],in[N],en[N],f[N],cnt,cn=0,s,ma[N];
stack<int>stk;
void add1(int u,int v,int va,double K){
	to[++cntt]=v;
	val[cntt]=va;
	k[cntt]=K;
	next[cntt]=head[u];
	head[u]=cntt;
}
void add2(int u,int v,int val,double K){
	to2[++cntt]=v;
	val2[cntt]=val;
	k2[cntt]=K;
	next2[cntt]=head2[u];
	head2[u]=cntt;
}
int get_val(int v,double k){
	int ans=v;
	k*=10;
	while(v){
		v*=k;
		v/=10;
		ans+=v;
	}
	return ans;
}
void dfs(int x){
	if(ma[x]){
		return ;
	}
	int ans=0;
	ans+=v[x];
	for(int i=head2[x];i;i=next2[i]){
		int y=to2[i];
		dfs(y);
		ans=max(ans,val2[i]+ma[y]);
	}
	ma[x]=ans;
}
void taj(int x){
	dfn[x]=++cnt;low[x]=dfn[x];
	stk.push(x);in[x]=1;
	for(int i=head[x];i;i=next[i]){
		int y=to[i];
		if(!dfn[y]){
			taj(y);
			low[x]=min(low[x],low[y]);	
		}
		else if(in[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(low[x]==dfn[x]){
		cn++;
		do{
			q=stk.top();stk.pop();
			in[q]=0;
			f[q]=cn;
		}while(q!=x);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,c,b;double d;
		scanf("%d%d%d",&a,&b,&c);
		cin>>d;
		val[i]=c;k[i]=d;
		add1(a,b,c,d);
	}
	scanf("%d",&s);
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			taj(i);
		}
	}
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=next[i]){
			int y=to[i];
			if(f[x]==f[y]){
				v[f[x]]+=get_val(val[i],k[i]);
			}
		}
	}
	cntt=0;
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=next[i]){
			int y=to[i];
			if(f[x]!=f[y]){
				add2(f[x],f[y],val[i],k[i]);
			}
		}
	}
	dfs(f[s]);
	printf("%d\n",ma[f[s]]);
	return 0;
}
2023/3/30 16:44
加载中...