30分求助

回复帖子

@Minagami_Yuki 2019-09-07 10:31 回复

#1#3#7过了,剩下的全WA了\ 尝试了两种写法,结果都是这样\ 自闭了

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    char ch = getchar(); int r = 0, w = 1;
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) {r = r * 10 + ch - '0', ch = getchar();}
    return r * w;
}

const int N = 1000010;
const int INF = 36501;

vector <int> g[N];
vector <int> G[N];

int n, m;
int in[N], dfn[N], low[N], scc[N], num[N], dp[N], tot, idx;
bool v[N];

stack <int> s;
queue <int> q;

inline void add(int x, int y) {
    g[x].push_back(y);
}

inline void Add(int x, int y) {
    G[x].push_back(y);
    in[y]++;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++idx;
    v[x] = 1;
    s.push(x);
    for(register int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if(v[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if(dfn[x] == low[x]) {
        tot++;
        while(s.top()) {
            int y = s.top();
            s.pop();
            scc[y] = tot;
            v[y] = 0;
            num[tot]++;
            if(num[tot] > 1) dp[tot] = INF;
            if(x == y) break;
        }
    }
}

inline void rebuild() {
    memset(v, 0, sizeof v);
    for(register int x = 1; x <= n + 1; x++) {
        for(register int i = 0; i < g[x].size(); i++) {
            int y = g[x][i];
            if(x == y) dp[scc[x]] = INF;
            if(scc[x] != scc[y]) {
                Add(scc[x], scc[y]);
            }
        }
    }
}

inline void TopSort() {
    q.push(scc[n + 1]);
    dp[scc[n + 1]] = 1;
    while(!q.empty()) {
        int x = q.front();
        v[x] = 1;
        q.pop();
        for(register int i = 0; i < G[x].size(); i++) {
            int y = G[x][i];
            dp[y] = min(dp[y] + dp[x], INF);
            in[y]--;
            if(!in[y]) q.push(y);
        }
    }
}

int main() {
    n = read(), m = read();
    for(register int i = 1; i <= m; i++) {
        int x = read(), y = read();
        add(y, x);
    }
    for(register int i = 1; i <= n + 1; i++) {
        if(!dfn[i]) tarjan(i);
    }
    rebuild();
    TopSort();
    int ans = 0, cnt = 0;
    for(register int i = 1; i <= n + 1; i++) {
        if(v[scc[i]]) ans = max(ans, dp[scc[i]]);
    }
    printf(ans == INF ? "zawsze" : "%d\n", ans);
    for(register int i = 1; i <= n + 1; i++) {
        if(v[scc[i]]) {
            if(dp[scc[i]] == ans) cnt++;
        }
    }
    printf("%d\n", cnt);
    for(register int i = 1; i <= n + 1; i++) {
        if(v[scc[i]]) {
            if(dp[scc[i]] == ans) printf("%d\n", i);
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。