Luogu P1983 – 拓扑排序

PROBLEM

https://www.luogu.org/problemnew/show/P1983

ANALYSIS

STL真的降智

做题之前被周围的人乱说一通更降智

题目大意：

构建低优先级车站指向高优先级车站的单向边，找关键路径。

跑一边拓扑排序就可以了。

使用set的时间约为不使用set时间的13-14倍，空间为5.5倍。也可能是我用的方法不对吧，但是慢是没的跑。

SOLUTION

// 213ms /  4.29MB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <set>

using namespace std;
using pii = pair<int, int>;

const int N = 1100;

int n, m;
vector<int> z[N];
bool b[N], v[N][N];
int ind[N], r[N];
queue<pii> q;

void gi(int & a) {
    char t = getchar();
    a = 0;
    for (; !isdigit(t); t = getchar());
    for (; isdigit(t); a *= 10, a += t - 48, t = getchar());
}


int main() {
    gi(n), gi(m);
    for (int i = 0, t, f; i < m; i++) {
        gi(t);
        memset(b, 0, sizeof(b));
        for (int j = 0; j < t; j++) {
            gi(f);
            r[j] = f;
            b[f] = 1;
        }
        for (int k = r[0]; k <= r[t - 1]; k++) {
            if (b[k]) {
                continue;
            }
            for (int l = 0, e; l < t; l++) {
                e = r[l];
                if (!v[k][e]) {
                    z[k].push_back(e);
                    v[k][e] = 1;
                    ind[e]++;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            q.push(make_pair(i, 1));
        }
    }
    pii u;
    int k, c;
    int ans = 0;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        k = u.first;
        c = u.second;
        ans = max(ans, c);
        for (auto e : z[k]) {
            if (--ind[e] == 0) {
                q.push(make_pair(e, c + 1));
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.