社区讨论

玄关求调!!为什么只有60分?

P1983[NOIP 2013 普及组] 车站分级参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhju7ype
此快照首次捕获于
2025/11/04 08:35
4 个月前
此快照最后确认于
2025/11/04 08:35
4 个月前
查看原帖
CPP
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 10010, M = 5010;

int ans;
int n, m;
int s[N], d[N];
int level[N];
int h[N], e[N], ne[N], idx;
bool st[N]; 
int vis[M][M]; // 修改为二维数组

inline void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

inline void bfs()
{
    queue<int> q;
    
    for(int i = 1; i <= n; i++)
    {
        if(!d[i]) 
        {
            level[i] = 1;
            q.push(i);
        }
    }
    
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(level[j] < level[t] + 1) // 确保取最大值
                level[j] = level[t] + 1;
            ans = max(ans, level[j]);    
            if(--d[j] == 0) 
                q.push(j);
        }    
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    memset(h, -1, sizeof h);
    
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        memset(st, 0, sizeof st);
        int len;
        cin >> len;
        for(int j = 1; j <= len; j++)
        {
            cin >> s[j];
            st[s[j]] = true;
        }
        
        for(int j = s[1]; j <= s[len]; j++)
        {
            if(!st[j])
            {
                for(int k = 1; k <= len; k++) // 修改循环范围
                {
                    if(!vis[j][s[k]])
                    {
                        vis[j][s[k]] = 1;
                        add(j, s[k]);
                        d[s[k]]++;
                    }
                }
            }
        }
    }
    
    ans = 0; // 初始化ans为0
    bfs();
            
    cout << ans << "\n";
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...