P2656 采蘑菇题解

银杉水杉秃杉 · 2021-12-02 08:34:53 · 题解

看到这道题所有题解都被撤了，我啪的一声就打开了博客，很快啊！

题是很简单的啊，我们就按题目给的标签（缩点 + spfa）做，不要整些歪门邪道的（像 dp 等什么的，跑的又慢还阴间）。

先跑 tarjan 缩点后图变成一个 DAG ，将每个强连通分量能采的蘑菇数算出来（包括恢复的蘑菇），最后跑 spfa 求最长路即可。相当于每到一个强连通分量就把它里面的蘑菇采光。

注意一点，这道题是不用开 double 的，刚开始记录恢复系数时乘以 10 就可以保证是 int 类型，求恢复的蘑菇是再整除以 10，这样就可以保证是向下取整的。

相信来做这道题的同学们都是会 spfa 和 tarjan 的哈，不会的建议可以先去学学再来做这道题，因为可能没有比这个更简单更容易理解的做法 QwQ

#include <bits/stdc++.h>
using namespace std;
const int N = 8e4 + 10, M = 2e5 + 10;
int n, m, t, cnt, tot, T, s, ans;
int head[N], dfn[N], low[N], vis[N];
int col[N], H[N], sum[N], dis[N], V[N];
struct edge
{
    int from, to, next, val, k;
} e[M], E[M];
stack<int> st;
queue<int> q;
void addedge(int u, int v, int w, int k)
{
    e[++t] = (edge){u, v, head[u], w, k};
    head[u] = t;
}
void add(int u, int v, int w)
{
    E[++T].to = v;
    E[T].next = H[u];
    E[T].val = w;
    H[u] = T;
}
void tarjan(int u)//tarjan缩点模板
{
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1;
    st.push(u);
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[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 (dfn[u] == low[u])
    {
        tot++;
        int v;
        do
        {
            v = st.top();
            st.pop();
            col[v] = tot;
            vis[v] = 0;
        } while (v != u);
    }
}
void spfa(int s)//spfa跑最长路
{
    memset(dis, -1, sizeof(dis));
    memset(V, 0, sizeof(V));
    dis[s] = sum[s];
    V[s] = 1;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        V[u] = 0;
        for (int i = H[u]; i; i = E[i].next)
        {
            int v = E[i].to, w = E[i].val;
            if (dis[v] < dis[u] + w + sum[v])
            {
                dis[v] = dis[u] + w + sum[v];
                if (!V[v])
                {
                    V[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        double k;
        scanf("%d%d%d%lf", &x, &y, &z, &k);
        addedge(x, y, z, k * 10);//先让恢复系数乘10
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= m; i++)
    {
        int x = e[i].from, y = e[i].to, z = e[i].val, k = e[i].k;
        if (col[x] == col[y])
            while (z)//同一个强连通分量就统计蘑菇数
            {
                sum[col[x]] += z;
                z = z * k / 10;//再整除10
            }
        else
            add(col[x], col[y], z);//不是同一个强连通分量就建边
    }
    scanf("%d", &s);
    s = col[s];
    spfa(s);
    for (int i = 1; i <= tot; i++)
        ans = max(ans, dis[i]);//终点是未知的，所以通过比较dis找到最长路
    printf("%d\n", ans);
    return 0;
}

顺便说说，人虽然退役了，题解还是要写的哈。

谢谢朋友们！

P2656 采蘑菇 题解

P2656 采蘑菇题解