求助 只对了前三个点
  • 板块P2656 采蘑菇
  • 楼主xu_TLE
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/10/20 11:49
  • 上次更新2023/10/27 06:48:58
查看原帖
求助 只对了前三个点
749554
xu_TLE楼主2022/10/20 11:49
#include<iostream>
#include<cctype>
#include<cstring>
#define int long long
using namespace std;
inline long long read(){
	long long x=0;char c=getchar();bool f=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+(c^48),c=getchar();
	return f?-x:x; 
}

int n,m,ss,ans[80011];
int k[200011],to[200011],f[200011],w[200011],nxt[200011],h[80011],cnt;
int s[80011],sd[80011],top,low[80011],dfn[80011],t,stac[80011];
bool vis[80011];

void add(int u,int v,int d,int r){
	to[++cnt]=v;
	w[cnt]=d;
	f[cnt]=u;
	nxt[cnt]=h[u];
	k[cnt]=r;
	h[u]=cnt;
}

void tarjan(int x){
	vis[x]=1;stac[++top]=x;
	dfn[x]=low[x]=++cnt;
	for(int y,i=h[x];i;i=nxt[i]){
		y=to[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(vis[y]){
			low[x]=min(dfn[y],low[x]);
		}
	}
	if(dfn[x]==low[x]){
		int y;
		++t;
		while(y=stac[top--]){
			vis[y]=0;
			sd[y]=t;
			if(x==y) break;
		}
	}
}

void re_add(int u,int v,int d){
	to[++cnt]=v;
	nxt[cnt]=h[u];
	w[cnt]=d;
	h[u]=cnt;
}

void rebuild(){
	memset(h,0,sizeof(h));
	for(int u,v,i=1;i<=m;i++){
		u=f[i],v=to[i];
		if(sd[u]!=sd[v]){
			re_add(sd[u],sd[v],w[i]);
		}
		else{
			int p=sd[u];
			while(w[i]){
				ans[p]+=w[i];
				w[i]=w[i]*k[i]/10;
			}
		}
	}
}

void dfs(int x){
	int d=0;
	for(int i=h[x];i;i=nxt[i]){
		dfs(to[i]);
		d=max(d,ans[to[i]]+w[i]);
	}
	ans[x]+=d;
}

signed main(){
	n=read(),m=read();
	for(int a,b,c,i=1;i<=m;i++){
		double d;
		a=read(),b=read(),c=read(),cin>>d;
		add(a,b,c,d*10);
	}
	ss=read();
	cnt=0;
	tarjan(ss);
	cnt=0;
	rebuild();
	dfs(sd[ss]);
	cout<<ans[sd[ss]];
}
2022/10/20 11:49
加载中...