60分萌新求助
查看原帖
60分萌新求助
188155
K2sen楼主2020/8/6 15:44

后几个数据中会出现这种情况

答案 400 919006 我输出0 0 是为啥

#include <bits/stdc++.h>
#define ll long long
#define N 1000010
#define M 100010

using namespace std;
int n, m, top, num, ans, point, add_edge, cnt, mod, ru[M], dis[M], d[M];
int head[N], col[M], dui[M], vis[M], sta[M], low[M], dfn[M], val[M], x[M], y[M], niu[M];
map<pair<int, int>, int> ma;
struct node {
    int next, to;
}edge[N];

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

void add(int from, int to) {
    edge[++add_edge].next = head[from];
    edge[add_edge].to = to;
    head[from] = add_edge;
}

void tarjan(int x) {
    low[x] = dfn[x] = ++cnt, sta[++top] = x, vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (!dfn[to]) tarjan(to), low[x] = min(low[x], low[to]);
        else if (vis[to]) low[x] = min(low[x], dfn[to]);
    }
    if (low[x] == dfn[x]) {
        num++;
        while (x != sta[top + 1]) {
            col[sta[top]] = num;
            vis[sta[top]] = 0;
            val[num]++;
            top--;
        }
    }
}

bool cmp(int a, int b) {
    if (x[a] != x[b]) return x[a] < x[b]; 
    return y[a] < y[b];
}

void link() {
    memset(head, 0, sizeof head), add_edge = 0;
    for (int i = 1; i <= m; i++) 
        if (ma[make_pair(col[x[i]], col[y[i]])] == 0 && col[x[i]] != col[y[i]]) {
            ma[make_pair(col[x[i]], col[y[i]])] = 1;
            add(col[x[i]], col[y[i]]), ru[col[y[i]]]++;
        }
}

void topo() {
    queue<int> q;
    for (int i = 1; i <= num; i++)
        if (!ru[i]) {
            q.push(i);
            dis[i] = val[i], dui[i] = 1;
            if (dis[ans] < dis[i]) point = i;
        }
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next) {
            int to = edge[i].to; ru[to]--;
            d[to] = 1;
            if (dis[to] < dis[x] + val[to]) {
                dis[to] = dis[x] + val[to];
                dui[to] = dui[x];
                if (dis[point] < dis[to]) point = to;
            }  
            if (dis[to] == dis[x] + val[to])
                dui[to] = (dui[to] + dui[x]) % mod;
            if (!ru[to]) q.push(to);
        }
        for (int i = 1; i <= num; i++)
            if (d[i] == 0) 
                if (dis[point] < dis[i]) point = i;
    }
}

int main() {
    n = read(), m = read(), mod = read();
    for (int i = 1; i <= m; i++) {
        x[i] = read(), y[i] = read();
        add(x[i], y[i]);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    link();
    topo();
    for (int i = 1; i <= num; i++)
        if (dis[i] == dis[point]) 
            ans = (ans + dui[i]) % mod;
    cout << dis[point] % mod << "\n" << ans;
}
2020/8/6 15:44
加载中...