P2656 采蘑菇

题目描述

小胖和ZYR要去ESQMS森林采蘑菇。

ESQMS森林间有N个小树丛，M条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。小胖和ZYR经过某条小径一次，可以采走这条路上所有的蘑菇。由于ESQMS森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数”，再下取整。

比如，一条路上有4个蘑菇，这条路的“恢复系数”为0.7，则第一~四次经过这条路径所能采到的蘑菇数量分别为4,2,1,0.

现在，小胖和ZYR从S号小树丛出发，求他们最多能采到多少蘑菇。

对于30%的数据，N<=7，M<=15

另有30%的数据，满足所有“恢复系数”为0

对于100%的数据，N<=80,000，M<=200,000，0.1<=恢复系数<=0.8且仅有一位小数，1<=S<=N.

输入输出格式

输入格式：

 

第一行，N和M

第2……M+1行，每行4个数字，分别表示一条小路的起点，终点，初始蘑菇数，恢复系数。

第M+2行，一个数字S

 

输出格式：

 

一个数字，表示最多能采到多少蘑菇，在int32范围内。

 

输入输出样例

输入样例#1： 

3 31 2 4 0.51 3 7 0.12 3 4 0.61

输出样例#1： 

8

 

啊啊啊，、、一般的操作、、、

我们先tarjan求一下强连通分量，然后因为强连通分量的每一个点之间都可以相互到达，那么也就是说强连通分量里的所有的蘑菇我们是都能得到的。然后我们在tarjan缩一下点，将一个强连通分量缩成一个点，这个点的权值即为这个强连通分量里的所有的蘑菇的个数，然后我们现在将一个带环的图转换成了一棵树型的结构，然后我们在跑一遍最长路就行了

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 200010using namespace std;queue
            
             q;bool vis[N];double recovery;int n,m,x,y,z,ns,top,tot,tim,tot1,sum,ans;int s[N],dfn[N],low[N],head[N],head1[N],stack[N],belong[N],dis[N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}struct Edge{ double rec; int to,dis,next,from;}edge[N],edge1[N];int add(int x,int y,int z,double rec){ tot++; edge[tot].to=y; edge[tot].dis=z; edge[tot].rec=rec; edge[tot].next=head[x]; head[x]=tot;}int add1(int x,int y,int z){ tot1++; edge1[tot1].to=y; edge1[tot1].dis=z; edge1[tot1].next=head1[x]; head1[x]=tot1;}int tarjan(int x){ dfn[x]=low[x]=++tim; stack[++top]=x,vis[x]=true; for(int i=head[x];i;i=edge[i].next) { int t=edge[i].to; if(vis[t]) low[x]=min(low[x],dfn[t]); else if(!dfn[t]) tarjan(t),low[x]=min(low[x],low[t]); } if(low[x]==dfn[x]) { sum++;belong[x]=sum,s[sum]++; for(;stack[top]!=x;top--) { z=stack[top]; belong[z]=sum,vis[z]=false,s[sum]++; } top--,vis[x]=false; }}int shink_point(){ for(int i=1;i<=n;i++) for(int j=head[i];j;j=edge[j].next) if(belong[i]==belong[edge[j].to]) if(s[belong[i]]>1) { x=edge[j].dis;dis[belong[i]]+=x; while(x) x*=edge[j].rec,dis[belong[i]]+=x; } for(int i=1;i<=n;i++) for(int j=head[i];j;j=edge[j].next) if(belong[i]!=belong[edge[j].to]) add1(belong[i],belong[edge[j].to],edge[j].dis);}int spfa(int ns){ vis[ns]=true,q.push(ns); while(!q.empty()) { x=q.front(),q.pop();vis[x]=false; for(int i=head1[x];i;i=edge1[i].next) { int t=edge1[i].to; if(dis[t]>dis[x]+edge1[i].dis) continue; dis[t]=dis[x]+edge1[i].dis; if(vis[t]) continue; vis[t]=true,q.push(t); } }}int main(){ n=read(),m=read(); for(int i=1;i<=m;i++) { x=read(),y=read(),z=read(); scanf("%lf",&recovery); add(x,y,z,recovery); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); shink_point();ns=read(); spfa(belong[ns]); for(int i=1;i<=sum;i++) ans=max(ans,dis[i]); printf("%d",ans); return 0;}