嗯...

?

聽說這是一道存圖+拓撲排序的題，但是看了一晚上好像只看出存圖來....

?

自己太蒟蒻，然后沒辦法，就.....就借用了Mr Kevin的代碼和思路，然后自己做了一些了解...

?

(并且現(xiàn)在自己對拓撲排序還不是那么了解....

?

首先先看一下題吧：

?

一條單向的鐵路線上，依次有編號為1,2,…,n的n個火車站。每個火車站都有一個級別，最低為1級。現(xiàn)有若干趟車次在這條線路上行駛，每一趟都滿足如下要求：如果這趟車次停靠了火車站 x，則始發(fā)站、終點站之間所有級別大于等于火車站x的都必須停靠。

(注意：起始站和終點站自然也算作事先已知需要停靠的站點）例如，下表是5趟車次的運行情況。其中，前4趟車次均滿足要求，而第 5 趟車次由于停靠了 3 號火車站(2級）卻未停靠途經(jīng)的 6號火車站（亦為2級）而不滿足要求。

?

現(xiàn)有 m 趟車次的運行情況（全部滿足要求），試推算這n個火車站至少分為幾個不同的級別。

輸入輸出格式

輸入格式：

第一行包含2個正整數(shù)n,m，用一個空格隔開。

第 i+1 行(1≤i≤m)中，首先是一個正整數(shù)si?(2≤si?≤n)，表示第i 趟車次有 si 個停靠站；接下來有si?個正整數(shù)，表示所有停靠站的編號，從小到大排列。每兩個數(shù)之間用一個空格隔開。輸入保證所有的車次都滿足要求。

輸出格式：

一個正整數(shù)，即n個火車站最少劃分的級別數(shù)。

輸入輸出樣例

輸入樣例#1： 9 2 4 1 3 5 6 3 3 5 6 輸出樣例#1： 2 輸入樣例#2：? 9 3 4 1 3 5 6 3 3 5 6 3 1 5 9 輸出樣例#2： 3

說明

對于20%的數(shù)據(jù)，1≤n,m≤10；

對于 50%的數(shù)據(jù)，1≤n,m≤100；

對于 100%的數(shù)據(jù)，1≤n,m≤1000。

?

下面說一下自己的理解的思路：

?

首先對這個題要有正確的理解：??

1.? 給出的一趟車，它所停靠的站點一定 >= 它所經(jīng)過站點中級別最小的點一定 >= 起始點和終點；

2.? 所有停靠的點的級別一定 > 未停靠的點；

3.? 根據(jù)大于關系建立有向無環(huán)圖(DAG) ，拓撲排序

?

?

所以，這道題的鬼畜之一在于——建圖：

不是將火車停靠的車站與下一個停靠車站之間建圖，而是將沒停靠的站點與其下一個停靠的車站構造一個有向無環(huán)圖（因為沒停靠的車站的級別一定比停靠的車站的級別要低...

?

這道題的鬼畜之二在于一個優(yōu)化：

實際上有最壞的情況,就是兩個點之間連了很多條邊（因為有很多趟車，不同趟的車可能經(jīng)過相同的站點），容易炸空間，所以就用vis數(shù)組進行標記，來簡化空間復雜度.....

?

所以，這道題的思路可分為：

?

優(yōu)化讀入----->建圖+vis優(yōu)化------>拓撲排序-------->輸出答案

?

下面是AC代碼：

1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 5 using namespace std; 6 7 inline int get_num() {//讀入優(yōu)化 8 int num = 0; 9 char c = getchar(); 10 while (c < '0' || c > '9') c = getchar(); 11 while (c >= '0' && c <= '9') 12 num = num * 10 + c - '0', c = getchar(); 13 return num; 14 } 15 16 const int maxn = 1005; 17 18 int graph[maxn][maxn], ind[maxn], stop[maxn], vis[maxn], level[maxn]; 19 //graph存圖，ind存點的入度，stop存車站，vis是否訪問（一個優(yōu)化），level存車站的級別 20 queue<int> q; 21 22 int main() { 23 int n = get_num(), m = get_num(), ans = 0; 24 for (int i = 1; i <= m; ++i) { 25 int s = 0, t = 0, cnt = get_num(); 26 memset(stop, 0, sizeof(stop)); 27 memset(vis, 0, sizeof(vis)); 28 for (int j = 1; j <= cnt; ++j) { 29 if (j == 1) vis[s = stop[j] = get_num()] = 1;//起點車站 30 else if (j == cnt) vis[t = stop[j] = get_num()] = 1;//終點車站 31 else vis[stop[j] = get_num()] = 1;//一般車站 32 } 33 for (int j = 1; j <= cnt; ++j) { 34 for (int k = s; k <= t; ++k) 35 if (!vis[k] && !graph[k][stop[j]])//k車站沒經(jīng)過并且還沒與車站j連成圖 36 graph[k][stop[j]] = 1, ++ind[stop[j]];//構建有向無環(huán)圖，j站入度+1 37 } 38 } 39 for (int i = 1; i <= n; ++i) 40 if (!ind[i]) { //沒有入度 41 level[i] = 1;//將級別設為1 42 q.push(i);//入隊，準備拓撲排序 43 } 44 while (!q.empty()) { 45 int u = q.front();//取隊首 46 q.pop(); 47 for (int v = 1; v <= n; ++v)//遍歷 48 if (graph[u][v]) {//如果u點與v點有一條邊 49 if (level[v] < level[u] + 1) 50 level[v] = level[u] + 1;//更新操作，因為所要到達的車站一定比前面那個沒有到達的車站的級別要高 51 if (!(--ind[v])) q.push(v);//toposort核心（判斷入度，并入隊 52 } 53 if (ans < level[u]) ans = level[u];//更新答案 54 } 55 printf("%d", ans); 56 return 0; 57 }

?

?

難點在于建圖，真搞不懂是如何想到這樣建圖的！！！

?

toposort也很重要！！！

?

轉(zhuǎn)載于:https://www.cnblogs.com/New-ljx/p/10498483.html

總結

以上是生活随笔為你收集整理的洛谷 P1983 车站分级的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。