P1983 [NOIP2013 普及组] 车站分级(用图论处理具有方向性的关系)

一开始想着记录一下每个站点的level,根据给出的关系进行调整,后来发现这种方法实际上稍微复杂一点的情况都解决不了,因为这里的关系是有连带的,处理A关系后可能破坏了B关系.

对于每一行数据,以"4 1 3 5 6"为例,它可以独立地表示这样的关系:

1,3,5,6站等级均高于2,4站,即在起点站与终点站之间没有停靠的站点的等级都比停靠了的站点等级低.停靠了的站点之间的关系是没有表明的.

我认为有效的一种解题思想,就是先把所有的关系存储在一种使得给定的所有关系都不发生矛盾的结构中,之后在这个结构中求最优解.这里站点之间要么有着具有方向性的关系,要么关系未知,尝试用以有向图的形式存储这些关系,显然图中不会出现环.

设A→B表示A站等级高于B站(?),以这组数据生成关系图:

(按照拓扑序对节点进行了分层,上层拓扑序靠前)

实际上,这组数据的最优解是3级,可以分为:

③ 1 5 8      1 5 8    
② 3 6 7  或  3 6
① 2 4        2 4 7

按照拓扑序分层(级),所得层数即为最优解.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> s[1010];
int n, m, deg[1010], ans;
bool pushed[1010][1010], used[1010];

int main() {
    scanf("%d%d", &n, &m);

    while (m--) {
        vector<int> from;
        int ct;
        scanf("%d", &ct);
        for (int i = 1, x; i <= ct; i++) {
            scanf("%d", &x);
            from.push_back(x);
        }

        for (int i = from[0], p = 0; i <= from[ct - 1]; i++) {
            if (p < from.size() && i == from[p]) {
                p++;
                continue;
            }
            for (auto j : from)
                if (!pushed[j][i]) {
                    s[j].push_back(i);
                    deg[i]++;
                    pushed[j][i] = true;
                }
        }
    }

    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int ct = q.size();
        while (ct--) {
            int cur = q.front();
            q.pop();
            for (auto i : s[cur]) {
                deg[i]--;
                if (!deg[i]) q.push(i);
            }
        }
        ans++;
    }

    printf("%d
", ans);

    return 0;
}

P1983

补充一题:

Cow Contest

给定N个个体,并给出他们之间的一些大小关系,判断有多少个个体在所有个体中的大小排名是确定的.

一个个体的排名确定,当且仅当比其大的个体数与比其小的个体数之和为N-1.

那么以个体为节点,大小关系为边建立有向图,A->B表示个体A大于个体B,那么如果某节点的入度与出度之和等于N-1,那么该节点表示的个体的排名才可确定.