目录

题目

P2656 采蘑菇

算法标签: 强连通分量, 缩点, 最长路, 最短路

思路

首先题目中给出的图是有向图, 每次采摘蘑菇之后当前位置的蘑菇数量会减少一定的值, 因此可以先缩点, 将每个联通分量内部的蘑菇都采摘完, 然后再求最长路也就是最大的蘑菇数量

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;

const int N = 8e4 + 10, M = 4e5 + 10;

int n, m, s;
int head1[N], head2[N], ed[M], ne[M], idx;
int fct[M], w[M];
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int scc_cnt, id[N];
int d[N], vals[N];

void add(int head[], int u, int v, int val, int weight) {
   
    ed[idx] = v, ne[idx] = head[u], fct[idx] = val, w[idx] = weight, head[u] = idx++;
}

void tarjan(int u) {
   
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    in_stk[u] = true;

    for (int i = head1[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (!dfn[v]) {
   
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
   
        ++scc_cnt;
        int ver;
        do {
   
            ver = stk[top--];
            in_stk[ver] = false;
            id[ver] = scc_cnt;
        } while (ver != u);
    }
}

void calc() {
   
    for (int u = 1; u <= n; ++u) {
   
        for (int i = head1[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (id[u] == id[v]) {
   
                int k = w[i];
                int r = fct[i];
                while (k > 0) {
   
                    vals[id[u]] += k;
                    k = k * r / 10;
                }
            }
        }
    }

    for (int u = 1; u <= n; ++u) {
   
        for (int i = head1[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            int a = id[u], b = id[v];
            if (a != b) {
   
                add(head2, a, b, 0, w[i]);
            }
        }
    }
}


void spfa() {
   
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(id[s]);
    d[id[s]] = vals[id[s]];
    bool vis[N] = {
   0};
    vis[id[s]] = true;

    while (!q.empty()) {
   
        int u = q.front();
        q.pop();
        vis[u] = false;

        for (int i = head2[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (d[u] + w[i] + vals[v] > d[v]) {
   
                d[v] = d[u] + w[i] + vals[v];
                if (!vis[v]) {
   
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head1, -1, sizeof head1);
    memset(head2, -1, sizeof head2);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v, weight;
        double val;
        cin >> u >> v >> weight >> val;
        add(head1, u, v, (int) (val * 10), weight);
    }
    cin >> s;

    for (int i = 1; i <= n; ++i) {
   
        if (!dfn[i]) tarjan(i);
    }

    calc();
    
    spfa();

    int ans = 0;
    for (int i = 1; i <= scc_cnt; ++i) ans = max(ans, d[i]);

    cout << ans << "\n";
    return 0;
}

数组模拟队列代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 8e4 + 10, M = 4e5 + 10;

int n, m, s;
int head1[N], head2[N], ed[M], ne[M], fct[M], w[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int scc_cnt, id[N];
int d[N], vals[N];

void add(int head[], int u, int v, int factor, int weight) {
   
    ed[idx] = v, ne[idx] = head[u], fct[idx] = factor, w[idx] = weight, head[u] = idx++;
}

void tarjan(int u) {
   
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    in_stk[u] = true;

    for (int i = head1[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (!dfn[v]) {
   
            tarjan(v);
            low[u]=  min(low[u], low[v]);
        }
        else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
   
        ++scc_cnt;
        int v;
        do {
   
            v = stk[top--];
            in_stk[v] = false;
            id[v] = scc_cnt;
        }
        while (v != u);
    }
}

void calc() {
   
    for (int u = 1; u <= n; ++u) {
   
        for (int i = head1[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            int scc1 = id[u], scc2 = id[v];
            if (scc1 == scc2) {
   
                int k = w[i];
                while (k > 0) {
   
                    vals[scc1] += k;
                    k = k * fct[i] / 10;
                }
            }
        }
    }

    for (int u = 1; u <= n; ++u) {
   
        for (int i = head1[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            int scc1 = id[u], scc2 = id[v];
            if (scc1 != scc2) add(head2, scc1, scc2, 0, w[i]);
        }
    }
}

void spfa() {
   
    int q[N], h = 0, t = -1;
    bool vis[N] = {
   0};
    int root = id[s];
    q[++t] = root;
    vis[root] = true;
    d[root] = vals[root];
    
    while (h <= t) {
   
        int u = q[h++];
        vis[u] = false;
        for (int i = head2[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (d[u] + w[i] + vals[v] > d[v]) {
   
                d[v] = d[u] + w[i] + vals[v];
                if (!vis[v]) {
   
                    q[++t] = v;
                    vis[v] = false;
                }
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head1, -1, sizeof head1);
    memset(head2, -1, sizeof head2);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        double fct;
        cin >> u >> v >> w >> fct;
        add(head1, u, v, (int) (fct * 10), w);
    }
    cin >> s;

    for (int i = 1; i <= n; ++i) {
   
        if (!dfn[i]) tarjan(i);
    }

    calc();
    spfa();

    int ans = 0;
    for (int i = 1; i <= scc_cnt; ++i) ans = max(ans, d[i]);

    cout << ans << "\n";
    return 0;
}