这道题是先用Tarjan缩点,告诉起点,然后拓扑求无向图最长路径

然而我一心以为只需要从起点开始拓扑就行了,其他不是路径上的点与s的正确路径又无关,但是这是错误的,

因为拓扑加点的条件是入度为0,不把那条边去掉的话,正确路径上的点也出不来,所以错了呀....

题目:https://www.luogu.com.cn/problem/P2656

代码:

#include<iostream>
#include<string>
#include<stack>
#include<stdio.h>
#include<queue>
#include<string.h>
#include<map>
#include<unordered_map>
#include<vector>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 6e5 + 100;
const int maxm = 6e5 + 100;
inline int r() {
    int f = 1, num = 0;
    char ch = getchar();
    while (0 == isdigit(ch)) { if (ch == '-')f = -1; ch = getchar(); }
    while (0 != isdigit(ch)) num = (num << 1) + (num << 3) + ch - '0', ch = getchar();
    return num * f;
}
struct edge {
    int from, to, next, w;
    double xishu;
}edge[maxm];
int tot1, hd[maxn];
void add_edge(int f, int to, int w, double x) {
    ++tot1;
    edge[tot1] = { f,to,hd[f],w,x };
    hd[f] = tot1;
}
struct E {
    int to, next, w;
}e[maxn];
int tot2, hd2[maxn];
void adde(int f, int to, int w) {
    tot2++;
    e[tot2] = { to,hd2[f],w };
    hd2[f] = tot2;
}
int fcn[maxn], low[maxn], vis[maxn], numcol, col[maxn], val[maxn], dis[maxn], du[maxn];
int cnt;
stack<int>S;
void Trajan(int rt) {

    fcn[rt] = low[rt] = ++cnt;
    vis[rt] = 1;
    S.push(rt);
    for (int i = hd[rt]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!fcn[v]) {
            Trajan(v);
            low[rt] = min(low[v], low[rt]);
        }
        else if (vis[v]) {
            low[rt] = min(low[rt], fcn[v]);
        }
    }
    if (low[rt] == fcn[rt]) {
        numcol++;
        //cout << "*" << numcol << endl;
        while (1) {
            int t = S.top(); S.pop();
            col[t] = numcol;
            vis[t] = 0;
            //cout << t << " ";
            if (t == rt)break;
        }
        //cout << endl;
    }
}
//int tuopu() {//错误的代码
//    queue<int>Q;
//    Q.push(col[s]);
//    int res = dis[st];
//    while (!Q.empty()) {
//        int t = Q.front(); Q.pop();
//        dis[t] += val[t];
//        res = max(res, dis[t]);
//        for (int i = hd2[t]; i; i = e[i].next) {
//            int v = e[i].to, w = e[i].w;
//            du[v]--;
//            //cout<<"&"<<t<<" "<< v << w << endl;
//            if (du[v] == 0)Q.push(v);
//            dis[v] = max(dis[v], dis[t] + w);
//        }
//    }
//    return res;
//}
int s;
int tuopu()
{
    queue<int>q;
    for (int i = 1; i <= numcol; i++)
    {
        if (!du[i])
            q.push(i);
        dis[i] = -0x7fffffff;
    }
    int ans = -0x7fffffff;
    dis[col[s]] = val[col[s]];
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = hd2[u]; i; i = e[i].next)
        {
            int v = e[i].to;
            dis[v] = std::max(dis[u] + e[i].w + val[v], dis[v]);
            du[v]--;
            if (!du[v])
                q.push(v);
        }
    }
    for (int i = 1; i <= numcol; i++)
        ans = std::max(ans, dis[i]);
    return ans;
}

int n, m;
int main() {
    //freopen("test.txt", "r", stdin);
    n = r(), m = r();
    for (int i = 1; i <= m; i++) {
        int st = r(), ed = r(), w = r();
        //cout <<"mm"<< st << " " << ed<<endl;
        double x; scanf("%lf", &x);
        add_edge(st, ed, w, x);
    }
    for (int i = 1; i <= n; i++) {
        if (!fcn[i]) {
            Trajan(i);
        }
    }
    for (int i = 1; i <= m; i++) {
        int u = edge[i].from, v = edge[i].to, w = edge[i].w;
        double x = edge[i].xishu;
        if (col[u] == col[v]) {
            while (w) {
                val[col[u]] += w;
                w *= x;
            }
        }
        else {
            //cout << u << v << endl;
            adde(col[u], col[v], w);
            du[col[v]]++;
        }
    }
    s = r();
    cout << tuopu() << endl;
    return 0;
}

View Code