题意:ESQMS森林间有N个小树丛，M条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇.小胖和ZYR经过某条小径一次，可以采走这条路上所有的蘑菇.由于ESQMS森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数”，向下取整.比如，一条路上有4个蘑菇，这条路的“恢复系数”为0.7，则第一~四次经过这条路径所能采到的蘑菇数量分别为4,2,1,0.现在，小胖和ZYR从S号小树丛出发，求他们最多能采到多少蘑菇.
分析:根据题意,只有强连通分量里面的边才能够采完所有蘑菇,其它的边只能采第一次的蘑菇数量.所以跑个有向图的(Tarjan)缩点.重新建图的时候,枚举每条边((u->v)),如果(u,v)不属于同一个强连通分量就直接加入新的图中,否则计算这条边会对这个强连通分量产生多少蘑菇贡献.
建图后直接从起点开始跑 既有边权又有点权 的最长路就好了.初始化的时候记得把起点的点权加进去.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=100005;
const int M=200005;
int n,m,S,ans,dis[N],a[M],b[M],c[M],size[N],in[N];
int tim,top,num,dfn[N],low[N],st[N],color[N];
int tot,head[N],nxt[M],to[M],w[M];
double d[M],ww[M];queue<int>q;
inline void add(int a,int b,int c,double d){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;ww[tot]=d;
}
inline void Add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
inline void tarjan(int u){
dfn[u]=low[u]=++tim;st[++top]=u;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!color[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
color[u]=++num;
while(st[top]!=u){
color[st[top]]=num;
--top;
}
--top;
}
}
inline int calc(int s,int hf){
int sum=0;
while(s){
sum+=s;
s=(int)s*hf;
}
return sum;
}
int main(){
n=read();m=read();
for(int i=1;i<=m;++i){
a[i]=read();b[i]=read();c[i]=read();cin>>d[i];
add(a[i],b[i],c[i],d[i]);
}
S=read();
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
tot=0;memset(head,0,sizeof(head));
for(int i=1;i<=m;++i){
if(color[a[i]]!=color[b[i]])
Add(color[a[i]],color[b[i]],w[i]);
else{//如果这条边在强连通分量里面就计算贡献
int s=w[i];
while(s){
size[color[a[i]]]+=s;
s=(int)s*ww[i];
}
}
}
memset(dis,-1,sizeof(dis));
q.push(color[S]);dis[color[S]]=size[color[S]];//初始化
while(q.size()){
int u=q.front();q.pop();in[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]<dis[u]+w[i]+size[v]){//最长路
dis[v]=dis[u]+w[i]+size[v];
if(!in[v])in[v]=1,q.push(v);
}
}
}
for(int i=1;i<=num;++i)ans=max(ans,dis[i]);//找到最大值
printf("%d
",ans);
return 0;
}