求助,#8 #9 MLE

P1983 [NOIP2013 普及组] 车站分级

vv123 @ 2020-08-11 17:37:31

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 3;
int n, m, s, t, ans, num, tmp, f[N], vis[N], in[N];
queue<int> q;
vector<int> g[N];
inline void toposort() {
    for (int i = 1; i <= n; i++) if (!in[i]) q.push(i), f[i] = 1;
  while (q.size()) {
    int u = q.front(); q.pop(); 
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        f[v] = f[u] + 1;
        ans = max(ans, f[v]);
        if(!--in[v]) q.push(v);
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        memset(vis, 0, sizeof(vis));
        cin >> num;
        for (int i = 1; i <= num; i++) {
            cin >> tmp;
            vis[tmp] = 1;
            if (i == 1) s = tmp;
            if (i == num) t = tmp;
        }
        for (int i = 1; i <= n; i++) 
        for (int j = s + 1; j < t; j++)
          if (vis[i] && !vis[j]) g[i].push_back(j), in[j]++;         
    }
    toposort();
    cout << ans;
    return 0;
}

by vv123 @ 2020-08-12 20:22:30

ee,判断一下重边然后就过了。


|