洛谷P2656题解

洛谷P2656题解。

题目分析

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

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

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

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

---

就是沿线采蘑菇，然后给定起点，没有给终点，蘑菇采完后会复活，复活的个数为上一次的个数×恢复系数。路是单向的，那么可以据此建一个有向图。如果一条边的两个顶点在同一个强连通分量内的话，那么这条边我可以经过无数次，这很容易证明。但是如果一条边的两个点不在同一个强连通分量，那么我只能采一次上面的蘑菇。因为题目没有规定不能反复横跳，所以我们可以先tarjan缩点然后把内部的边权集中到点上，再集中的时候只需要注意一定是要×系数累加上去的，因为我能无数次经过。

缩点之后就是对DAG处理，我看大佬们用的都是最短路径算法，这里菜鸡只会拓扑排序qwq。

这里还需要注意的是，起点所在的强连通分量如果入读不为0那么那些蘑菇我是采不到的。因此我在这里设立一个flag标记，在拓扑排序的时候如果flag为0那么我只把点和边删了，不做数值上的处理。然后我对起点所在的强连通分量flag设1，然后如果flag为1则会向后面的点传递。

在写状态转移方程的时候注意要把路上的蘑菇和那个点的蘑菇都加上。

如果路径上的蘑菇为w，v强连通分量上的蘑菇数为$amount[v]$。那么$u->v$的状态转移方程就应该是

$ans[v]=max(ans[v],ans[u]+w+amount[v])$

最后注意一个，那就是一定要记着不管怎样给最终结果赋一个初始值就是起点所在强连通分量的蘑菇数量，这里卡了一下。

下面给出AC代码。

#include<bits/stdc++.h>
#define maxn 80005
using namespace std;
struct eee{
    int to;
    int next;
    int w;
    float p;
}edge[maxn*3],e[maxn*3];
int root[maxn],root2[maxn],dfn[maxn],low[maxn],visited[maxn],s[maxn],degree[maxn],num[maxn],amount[maxn],ans[maxn],flag[maxn],cnt,cnt2,tot,top,deep,n,m;
stack<int>ss;//拓扑排序用的栈
void add(int x,int y,int w,float p){//一开始的建图
    edge[++cnt].to=y;
    edge[cnt].w=w;
    edge[cnt].next=root[x];
    edge[cnt].p=p;
    root[x]=cnt;
}
void add2(int x,int y,int w,float p){//强连通分量的建图
    degree[y]++;
    e[++cnt2].next=root2[x];
    e[cnt2].to=y;
    e[cnt2].w=w;
    e[cnt2].p=p;
    root2[x]=cnt2;
}
void tarjan(int u){//tarjan板子
    visited[u]=1;
    dfn[u]=low[u]=++deep;
    s[++top]=u;
    for(int i=root[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(visited[v]){
            low[u]=min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u]){
        visited[u]=0;
        num[u]=++tot;
        while(s[top]!=u){
            visited[s[top]]=0;
            num[s[top--]]=tot;
        }
        top--;
    }
}
int main(){
    //freopen("1.txt","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y, w;
        float p;
        cin>>x>>y>>w>>p;
        add(x,y,w,p);
    }
    int start;
    scanf("%d",&start);
    
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    
    for(int i=1;i<=n;i++){
        for(int j=root[i];j;j=edge[j].next){
            int v=edge[j].to,w=edge[j].w;
            float p=edge[j].p;
            if(num[i]==num[v]){//同一个强连通分量内则把所有能产生的蘑菇加上
                while(w!=0){
                    amount[num[i]]+=w;
                    w=(int)((p)*w);
                }
            }
            else{
                add2(num[i],num[v],w,p);//否则建边
            }
        }
    }
    
    for(int i=1;i<=tot;i++){
        if(!degree[i])ss.push(i);
    }
    ans[num[start]]=amount[num[start]];
    flag[num[start]]=1;
    int res=ans[num[start]];//res一定赋初值不要忘了
    while(!ss.empty()){
        int x=ss.top();
        ss.pop();
        for(int i=root2[x];i;i=e[i].next){
            int v=e[i].to,w=e[i].w;
            degree[v]--;
            if(!degree[v])ss.push(v);
            if(flag[x]){
                ans[v]=max(ans[v],ans[x]+w+amount[v]);//状态转移方程
                res=max(res,ans[v]);//保存结果
                flag[v]=1;//flag向前传播
            }
        }
    }
    if(tot==1){
        printf("%d",ans[1]);
    }    
    else 
        printf("%d",res);
    return 0;
}