[NOIP2013]车站分级

解题报告

被一道普及组的题卡了这么长时间,不开心。调了两三天,发现cnt=0;放错位置了。 至于原题,COGS 经(简)典(单)的拓扑排序,数据范围还这么小。。。

#include 
#include 
#include 
#include 
#include 
using namespace std;
queue  q;
int n, m, in[1005], b[1005],level;
bool map[1005][1005], a[1005];
inline int get_num()
{
    int ans = 0;
    char tmp;
    tmp = getchar();
    while (tmp > '9' || tmp < '0')    tmp = getchar();
    while (tmp <= '9'&&tmp >= '0')
    {
        ans = ans * 10 + tmp - 48;
        tmp = getchar();
    }
    return ans;
}
int main()
{
    freopen("level2013.in", "r", stdin);
    freopen("level2013.out", "w", stdout);
    int si, tmp, cnt;
    n = get_num();
    m = get_num();
    for (int i = 1; i <= m; i++)
    {
        cnt = 0;
        si = get_num();
        memset(a, 0, sizeof(a));
        for (int j = 1; j <= si; j++)
        {
            tmp = get_num();
            b[++cnt] = tmp;
            a[tmp] = true;
        }
        for (int j = b[1]; j <= b[cnt]; j++)
        {
            if (!a[j])
            {
                for (int k = 1; k <= cnt; k++)
                {
                    if (!map[j][b[k]])
                    {
                        map[j][b[k]] = 1;
                        in[b[k]]++;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!in[i])
            q.push(i);
    }
    while (!q.empty())
    {
        si = q.size();
        level++;
        for (int i = 1; i <= si; i++)
        {
            int ti = q.front();
            q.pop();
            for (int j = 1; j <= n; j++)
            {
                if (map[ti][j])
                {
                    in[j]--;
                    if (!in[j])
                        q.push(j);
                }
            }
        }
    }
    cout << level << "\n";
    return 0;
}

 

2 thoughts on “[NOIP2013]车站分级”

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理