30pts求调球求了啦
查看原帖
30pts求调球求了啦
1351669
yangruixi0728楼主2025/1/31 12:09
#include<bits/stdc++.h>
using namespace std;
const int N=80010,M=200010;
int n,m,s,ans,sum[N];
int h[N],e[M],ne[M],w[M],p[M],idx,f[M];
int he[N],e2[M],ne2[M],w2[M],idx2;
int low[N],dfn[N],timestamp;
int stk[N],top,id[N],scc_cnt;
int Size[N],dist[N],vis[N];
bool in_stk[N];
inline void add(int a,int b,int c,int d){
	e[idx]=b,f[idx]=a,w[idx]=c,p[idx]=d,ne[idx]=h[a],h[a]=idx++;
}
inline void add2(int a,int b,int c){
	e2[idx2]=b,w2[idx2]=c,ne2[idx2]=he[a],he[a]=idx2++;
}
void tarjan(int u){
	low[u]=dfn[u]=++timestamp;
	stk[++top]=u;
	in_stk[u]=1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(!dfn[j]){
			tarjan(j);
			low[u]=min(low[u],low[j]);
		}
		else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
	}
	if(low[u]==dfn[u]){
		int y;
		++scc_cnt;
		do{
			y=stk[top--];
			in_stk[y]=0;
			id[y]=scc_cnt;
			Size[scc_cnt]++;
		}while(y!=u);
	}
}
void spfa(int s){
	queue<int> q;
	memset(dist,0,sizeof 0);
	memset(vis,0,sizeof vis);
	ans=dist[s]=sum[s];
	vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int t=q.front();
		q.pop();
		vis[t]=0;
		for(int i=he[t];~i;i=ne2[i]){
			int j=e2[i];
			if(dist[j]<dist[t]+w2[i]+sum[j]){
				dist[j]=dist[t]+w2[i]+sum[j];
				ans=max(ans,dist[j]);
				if(!vis[j]){
					q.push(j);
					vis[j]=1;
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	memset(he,-1,sizeof he);
	for(int i=1;i<=m;i++){
		int x,y,c;
		double d;
		scanf("%d%d%d%lf",&x,&y,&c,&d);
		d*=10;
		add(x,y,c,d);
	}
	scanf("%d",&s);
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=h[i];~j;j=ne[j]){
			int x=i;
			int y=e[j];
			int z=w[j];
			int k=p[j];
			if(id[x]==id[y]){
				sum[id[x]]+=w[j];
				z=z*k/10;
			}
			else add2(id[x],id[y],z);
		}
	}
	spfa(id[s]);
	printf("%d",ans);
	return 0;
}
2025/1/31 12:09
加载中...