Tarjan30pt求助
  • 板块P2656 采蘑菇
  • 楼主Grimgod
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/16 07:47
  • 上次更新2023/10/27 20:06:38
查看原帖
Tarjan30pt求助
495512
Grimgod楼主2022/7/16 07:47
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int w=0,x=0;char ch;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}
int sccnum;
int sccval[100005];
int sccid[100005];
int g,h;
int n,m;
int p;
struct edge{
	int to,l;
	int fr;
	edge (int to,int l,int fr) :to(to),l(l),fr(fr){}
};
vector <edge > e[100005],enew[100005];
inline void add(int u,int v,int len,int fr){
	e[u].push_back(edge(v,len,fr));
}
int in[100005],out[100005];
int low[100005],dfn[100005];
int a[100005];
int cnt;
bool ins[100005];
stack <int > s;
inline void tarjan(int now){
	dfn[now]=low[now]=++cnt;
	s.push(now),ins[now]=1;
	for(register int i=0;i<e[now].size();++i){
		register int to=e[now][i].to;
		if(!dfn[to]){
			tarjan(to);
			low[now]=min(low[now],low[to]);
		}
		else if(ins[to]){
			low[now]=min(low[now],dfn[to]);
		}
	}
	if(low[now]==dfn[now]){
		sccnum++;
		register int y=0;
		do{
			y=s.top();
			s.pop();
			sccid[y]=sccnum;
			ins[y]=0;
		}while(now!=y);
	}
}
inline void addnew(int u,int v,int len){
	enew[u].push_back(edge(v,len,0));
	in[v]++;
	out[u]++;
}
inline void build(){
	for(register int i=1;i<=n;++i){
		for(register int j=0;j<e[i].size();++j){
			register int to=e[i][j].to,l=e[i][j].l,fr=e[i][j].fr;
			if(sccid[i]==sccid[to]){
				register int kkk=0;
				while(l){
					kkk+=l;
					l*=fr;
					l/=10;
				}
				sccval[sccid[i]]+=kkk;
			}
			else addnew(sccid[i],sccid[to],l);
		}
	}
}
int ph;
double xs[100005];
int dis[100005];
bool vis[100005];
int cn[100005];
int st;
int ss;
inline void topo(){
	queue <int > q;
	for(register int i=1;i<=sccnum;++i){
		if(in[i]==0){
			q.push(i);
			dis[i]=-0x3f3f3f3f;
		}
	}
	dis[st]=sccval[st];
	while(!q.empty()){
		register int now=q.front();
		q.pop();
		for(register int i=0;i<enew[now].size();++i){
			register int to=enew[now][i].to;
			dis[to]=max(dis[to],dis[now]+enew[now][i].l+sccval[to]);
			in[to]--;
			if(in[to]==0) q.push(to);
		}
	}
}
int main(){
	n=read(),m=read();
	for(register int i=1;i<=m;++i){
		 g=read(),h=read(),ph=read();
		 cin>>xs[i];
		 add(g,h,ph,xs[i]*10);
	}
	ss=read();
	for(register int i=1;i<=n;++i){
		if(!dfn[i]) tarjan(i);
	}
	build();
	st=sccid[ss];
	topo();
	register int maxi=0;
	for(register int i=1;i<=sccnum;++i) {
		maxi=max(maxi,dis[i]);
		//cout<<dis[i]<<" ";
	}
	cout<<maxi;
	return 0;
} 
2022/7/16 07:47
加载中...