题目大意：
小胖和ZYR要去ESQMS森林采蘑菇。
ESQMS森林间有N个小树丛，M条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。小胖和ZYR经过某条小径一次，可以采走这条路上所有的蘑菇。由于ESQMS森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数”，再下取整。
比如，一条路上有4个蘑菇，这条路的“恢复系数”为0.7，则第一~四次经过这条路径所能采到的蘑菇数量分别为4,2,1,0.
现在，小胖和ZYR从S号小树丛出发，求他们最多能采到多少蘑菇。
分析：
1、题目没有限定路走的次数，显然如果图中有强连通分量（即有向环），那么这个环中的所有边都可以无数次访问，直到所有边能采到的蘑菇数量为 0 ，即为该连通分量的最大价值，故先进行缩点。
2、缩点之后，全图变为DAG图，然后每个点有价值，其次每条边有价值（且这个价值不会再乘以 恢复系数 ，因为缩点后不可能再走第二次）。那么求一些缩点与边权的最大价值，故用 DP 解答。
3、本题还要注意的是，它会给你一个起点，所以在拓扑排序中，在这个起点上面的点可以直接忽略，当然我们也可以全部初始化为负无穷，然后设起点 DP 值为该点的价值（如果这个起点是缩点的话，否则价值是 0 的），这样求最大值的时候，所有状态只会从起点转移，就不用将起点上面的点排除了，更方便。
代码如下：
#include<iostream> #include<algorithm> #include<string.h> #include<queue> #define maxn 80008 using namespace std; int n,m,cnt,tot,Index,sum,st; int low[maxn],dfn[maxn],flag[maxn],head[maxn],q[maxn]; int pre[maxn],s[maxn],in[maxn],qhead[maxn]; int b[maxn],dp[maxn]; bool vis[maxn]; struct Edge { int to; int val; double t; int next; }edge[200008]; struct EDGE { int to; int val; int next; }E[200008]; inline void add(int u,int v,int w,double t) { edge[++cnt].to=v; edge[cnt].val=w; edge[cnt].t=t; edge[cnt].next=head[u]; head[u]=cnt; return; } inline void qadd(int u,int v,int w) { E[++cnt].to=v; E[cnt].val=w; E[cnt].next=qhead[u]; qhead[u]=cnt; return; } void tarjan(int u) { low[u]=dfn[u]=++Index; q[++tot]=u; vis[u]=true; for(int i=head[u];i;i=edge[i].next){ int v=edge[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ++sum;//缩点的序号 do{ pre[q[tot]]=sum; vis[q[tot--]]=false; }while(q[tot+1]!=u); } return; } void topo() { queue<int> Q; while(!Q.empty()) Q.pop(); for(int i=1;i<=sum;i++){ if(!in[i]) Q.push(i); } while(!Q.empty()) { int x=Q.front(); Q.pop(); b[++cnt]=x,dp[x]=-0x3f3f3f3f;//记住要初始化为负无穷，不然会 WA 一个点 for(int i=qhead[x];i;i=E[i].next){ int v=E[i].to; in[v]--; if(!in[v]) Q.push(v); } } return; } int main() { //freopen("test.in","r",stdin); //freopen("test.out","w",stdout); scanf("%d%d",&n,&m); int A,B,C; double D; for(int i=1;i<=m;i++){ scanf("%d%d%d%lf",&A,&B,&C,&D); add(A,B,C,D); } scanf("%d",&st); for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);} cnt=0; for(int i=1;i<=n;i++){ for(int j=head[i];j;j=edge[j].next){ int v=edge[j].to; if(pre[i]!=pre[v]){qadd(pre[i],pre[v],edge[j].val);in[pre[v]]++;} else{ int ans=edge[j].val; int res=edge[j].val*edge[j].t; while(res){ //算这个缩点的总价值，即按题意把所有边乘到为 0 ans+=res; res=res*edge[j].t; } s[pre[i]]+=ans; } } } cnt=0; topo();//保证有向图 DP 顺序 dp[pre[st]]=s[pre[st]];//标记从起点所代表的缩点上为初始态转移 for(int i=1;i<=cnt;i++){ int u=b[i]; for(int j=qhead[u];j;j=E[j].next){ int v=E[j].to; dp[v]=max(dp[v],dp[u]+E[j].val+s[v]); } } int ans=-0x3f3f3f3f; for(int i=1;i<=cnt;i++) ans=max(ans,dp[i]); printf("%d ",ans ); }