拓扑 50 pts 求助!在线等!救救孩子吧!

P1983 [NOIP2013 普及组] 车站分级

_lucky__dog_ @ 2022-01-17 13:02:21

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, m, top, ans;
int s;
int st[1010], d[1010], g[1010][1010], c[1010];
int q[1010];
int w[1010]; //表示每个车站的层数。 
bool v[1010], mp[1010][1010];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i ++ )
    {
        memset(v, 0, sizeof v);

        scanf("%d", &s);

        for (int j = 1; j <= s; j ++ )
        {
            scanf("%d", &st[j]); v[st[j]] = 1; 
        }
        for (int j = st[1]; j <= st[s]; j ++ )
        {
            if(v[j]) continue;

            for (int k = 1; k <= s; k ++ )
            {
                if(mp[st[k]][j]) continue;
                mp[st[k]][j] = 1; //连一条从 a[k] 到 j 的有向边,代表 a[k] 的级别大于 j。
                d[j] ++; //更新一下 j 的入度。 
                g[st[k]][++ c[st[k]]] = j;
            }
        }
    }
    for (int i = 1; i <= n; i ++ )
    {
        if(d[i] == 0) q[++ top] = i, w[i] = 1;

    }   
    while (top)
    {
        int t = q[top];
        top --;
        for (int i = 1; i <= c[t]; i ++ )
        {
            int v = g[t][i];
            d[v] --;
            w[v] = w[t] + 1;
            ans = max(ans, w[v]);
            if(d[v] == 0) q[++ top] = v;
        }
    }
    printf("%d", ans);

    return 0; 
}

by bamboo12345 @ 2022-03-19 09:10:26

@努力的邱_Hella

 w[v] = w[t] + 1;

这句不对,应改为

w[v] = max(w[v], w[t] + 1);

因为这个点我们要取最大指向它的


by _lucky__dog_ @ 2022-03-21 18:14:32

@bamboo123 谢谢,已经 AC 了


|