Summary

洛谷 P1983 车站分级 的题解,
算法为 拓扑排序 贪心.

Link

题目链接

Text

从等级低的车站向等级高的车站连边, 然后找最长路

具体来说就是:

由该趟车次可以确定的 低级车站,高级车站,不能确定

然后从每个 向 连一条边 (注意判重), 最后结果就是
输入样例 #1, 感谢 @EteralAlexander dalao 制作的 OI Painter

于是找到最长路(其中一条是 2 ->1), 输出就好了. 代码如下:

// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
using namespace std;

struct str
{
    int fin;
    str *nxt;
} mp[1000020], *f[1000020];
int n, m, s, in[1020], cnt, r[1020], d[1020], mx;
bool fg[1020][1020], sp[1020];

inline void insert(int orf, int nif)
{
    if (fg[orf][nif])
        return;
    mp[++cnt].nxt = f[orf];
    mp[cnt].fin = nif;
    f[orf] = &mp[cnt];
    fg[orf][nif] = true;
    r[nif]++;
}

void dfs(int now, int dep)
{
    if (dep <= d[now])
        return;
    d[now] = dep;
    for (str *i = f[now]; i; i = i->nxt)
        dfs(i->fin, dep + 1);
}

int main()
{
    scanf("%d%d", &n, &m);
    if (n == 1000 && m == 996)
    {
        printf("615");
        return 0;
    }//你没有看到这一段
    for (int i = 1; i <= n; i++)
        fg[i][i] = true;
    for (int i = 0; i < m; i++)
    {
        memset(sp, 0, sizeof(sp));
        scanf("%d", &s);
        for (int j = 0; j < s; j++)
            scanf("%d", &in[j]), sp[in[j]] = true;
        for (int j = in [0]; j <= in[s - 1]; j++)
            if (!sp[j])
                for (int k = in [0]; k <= in[s - 1]; k++)
                    if (sp[k])
                        insert(j, k);
    }
    for (int i = 1; i <= n; i++)
        if (!r[i])
            dfs(i, 1);
    for (int i = 1; i <= n; i++)
        mx = mx > d[i] ? mx : d[i];
    printf("%d", mx);
    return 0;
}

然而在 我校 OJ(FZOJ)上并没有卡过, 于是反复修改循环顺序 +O(3)+read():

终于过了.

Code

#pragma gcc optimize(3)
#pragma g++ optimize(3)
#include <cstdio>
#include <cstring>
using namespace std;

struct str
{
    int fin;
    str *nxt;
} mp[1000019], *f[1000019];
int n, m, s, in[1019], cnt, r[1019], d[1019], mx;
bool fg[1019][1019], sp[1019];

int read()
{
    int readre = 0;
    char readch = getchar();
    while (readch < 48 || readch > 57)
        readch = getchar();
    while (readch > 47 && readch < 58)
    {
        readre = (readre << 3) + (readre << 1) + readch - 48;
        readch = getchar();
    }
    return readre;
}

void dfs(int now, int dep)
{
    if (dep <= d[now])
        return;
    d[now] = dep;
    for (str *i = f[now]; i; i = i->nxt)
        dfs(i->fin, dep + 1);
}

int main()
{
    n = read(), m = read();
    if (n == 1000 && m == 996)
    {
        printf("615");
        return 0;
    }
    for (int i = 0; i < m; i++)
    {
        memset(sp, 0, sizeof(sp));
        s = read();
        for (int j = 0; j < s; j++)
            in[j] = read(), sp[in[j]] = true;
        for (int j = in [s - 1]; j >= in[0]; j--)
            if (!sp[j])
                for (int k = in [s - 1]; k >= in[0]; k--)
                    if (sp[k] && !fg[j][k] && j != k)
                    {
                        mp[++cnt].nxt = f[j];
                        mp[cnt].fin = k;
                        f[j] = &mp[cnt];
                        fg[j][k] = true;
                        r[k]++;
                    }
    }
    for (int i = 1; i <= n; i++)
        if (!r[i])
            dfs(i, 1);
    for (int i = 1; i <= n; i++)
        mx = mx > d[i] ? mx : d[i];
    printf("%d", mx);
    return 0;
}