20pts求助,WA的全为输出0
查看原帖
20pts求助,WA的全为输出0
1287433
__ycy1124__楼主2024/11/13 20:31
#include<bits/stdc++.h>
#define N 80005
#define double long double
using namespace std;
struct road{
	int to,w;
	double v;
};
vector<road>a[N];
int dfn[N],low[N],color[N],Color,idx;
stack<int>q;
int w[N],n,m; 
bool bj[N];
void dfs(int p){
	bj[p]=1;
	dfn[p]=low[p]=++idx;
	q.push(p);
	for(auto it:a[p]){
		if(!dfn[it.to]){
			dfs(it.to);
			low[p]=min(low[p],low[it.to]);
		}
		else{
			if(bj[it.to]){
				low[p]=min(low[p],dfn[it.to]);
			}
		}
	}
	if(dfn[p]==low[p]){
		++Color;
		while(q.top()!=p){
			bj[q.top()]=0;
			color[q.top()]=Color;
//			js[Color]++;
			q.pop();
		}
		bj[p]=0;
		q.pop();
		color[p]=Color;
//		js[Color]++;
	}
}
void tarjan(){
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i);
		}
	}
}
int ans=0;
vector<int>qaq[N];
map<int,int>t[N];
void ddfs(int p,int ww){
	ww+=w[p];
	ans=max(ans,ww);
	for(auto it:qaq[p]){
		ddfs(it,ww+t[p][it]);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		double qwq;
		cin>>u>>v>>w>>qwq;
		a[u].push_back({v,w,qwq});
	}
	int s;
	cin>>s;
	tarjan();
	for(int i=1;i<=n;i++){
		for(auto it:a[i]){
			if(color[it.to]==color[i]){
				int ww=it.w;
				while(ww!=0){
					w[color[i]]+=ww;
					ww*=it.v;
				}
			}
			else{
				t[i][it.to]+=it.w;
				qaq[i].push_back(it.to);
			}
		}
	}
	ddfs(s,0);
	cout<<ans;
	return 0;
}
2024/11/13 20:31
加载中...