tarjan 求助
查看原帖
tarjan 求助
420102
phmaprostrate楼主2021/11/4 21:25

没有小数好像也错了,

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 8e4 + 10;
const int M = 2e5 + 10;
int n,m,t;
int from[M],to[M],ww[M];
long  double zz[M];
struct node {
	int to,next,w;
	long  double z;
} tr[2 * M];
int h[N],k = 0;
void add(int from,int to,int w,double z) {
	tr[++k].to = to;
	tr[k].w = w;
	tr[k].z = z;
	tr[k].next = h[from];
	h[from] = k;
}
int dfn[N],low[N],num = 0;
int id[N],s[N],ins[N],cnt = 0,top = 0;
int sum[N];
void tarjan(int x) {
	low[x] = dfn[x] = ++ num;
	ins[x] = true,s[++top] = x;
	for(int i = h[x] ; i ; i = tr[i].next) {
		int y = tr[i].to;
		if(!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x],low[y]);
		} else if(ins[y]) low[x] = min(low[x],dfn[y]);
	}
	if(dfn[x] == low[x]) {
		int z;
		cnt ++;
		do {
			z = s[top--];
			id[z] = cnt;
			ins[z] = false;
		} while(z != x);
	}
}
int d[N],vis[N];
queue<int> q;
void spfa(int x){
	memset(d,-0x3f,sizeof(d));
	d[x] = sum[x],q.push(x),vis[x] = true;
	while(!q.empty()){
		int u = q.front();
		q.pop(),vis[u] = true;
		for(int i = h[u] ; i ; i = tr[i].next){
			int y = tr[i].to,w = tr[i].w;
			if(d[y] < d[u] + w + sum[y]){
				d[y] = d[u] + w + sum[y];
				if(!vis[y]){
					q.push(y);
					vis[y] = true;
				}
			}
		}
	}
	int ans = 0;
   for(int i = 1 ; i <= cnt ; i ++) ans = max(ans,d[i]);
   cout <<ans;
}
signed main() {
//	freopen("p2454 tarjan.in","r",stdin);
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i ++) {
		int u,v,w;
		 long double z;
		cin >> u >>v >> w >> z;
		from[i] = u,to[i] = v,ww[i] = w,zz[i] = z;
		add(u,v,w,z);
	}
	cin >>t;
	for(int i = 1 ; i <= n ; i ++) {
		if(!dfn[i]) tarjan(i);
	}
	memset(tr,0,sizeof(tr)),memset(h,0,sizeof(h)),k = 0;
    for(int i = 1 ; i <= m ; i ++){
    	int a = id[from[i]],b = id[to[i]];
    	if(a != b){
    		add(a,b,ww[i],0);
		}
		else{
			int w = ww[i];
			while(w){
				sum[b] += w ;
				w = (int)w * zz[i];
			}
		}
	}
	spfa(id[t]);
	return 0;
}

2021/11/4 21:25
加载中...