NOIP2013普及组 车站分级

一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。

每个火车站都有一个级别，最低为 1 级。

现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点） 

例如，下表是 5 趟车次的运行情况。

其中，前 4 趟车次均满足要求，而第 5 趟车次由于停靠了 3 号火车站（2 级）却未停靠途经的 6 号火车站（亦为 2 级）而不满足要求。

现有 m 趟车次的运行情况（全部满足要求），试推算这 n 个火车站至少分为几个不同的级别。

输入格式

第一行包含 2 个正整数 n,m，用一个空格隔开。

第 i+1 行（1≤i≤m）中，首先是一个正整数 si（2≤si≤n），表示第 i 趟车次有 si 个停靠站；接下来有 si 个正整数，表示所有停靠站的编号，从小到大排列。

每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出格式

输出只有一行，包含一个正整数，即 n 个火车站最少划分的级别数。

数据范围

1≤n,m≤1000

输入样例：

9 3 
4 1 3 5 6 
3 3 5 6 
3 1 5 9 

输出样例：

3

难度：中等

时/空限制：1s / 64MB

总通过数：2510

总尝试数：5347

来源：NOIP2013普及组

算法标签

解题思路：

由题意停靠的车站必然比非停靠的车站级别高

因此我们可以把一条线路中非停靠站和停靠站连一条权值为1的边：如样例：1，3，5，6.

所连接的边为：

 

 因为题目保证一定有解所以该图肯定无环即为拓扑图。

但是这样建图的一个车次的边数为n * (1000 - n)（即非停靠点的点数n * 剩下的点数即停靠点的点数(1000 - n)）最多有1000个车次即共需要建1000 * n * (1000 - n)条边，当n取500是上述式子取最大值即为1000 * 500 * 500这样肯定会tle所以不能这样建边。

这里有一个非常常用的算法，在非停靠点和停靠点之间建立一个虚拟点，非停靠点到虚拟点的权值定义为0，虚拟点到停靠点的权值定义为1：

如图：

这样的建边方式与上述的建边方式是等价的，因此所建立的边数从n * (1000 - n)变为n + 1000 - n; 因此边数最多为为1000  * （500 + 500）

#include 
#include 
#include 
 
using namespace std;
 
const int N = 2010, M = 1000 * 1000 + 10;
 
int n, m;
int d[N];//记录一个点的入度
bool st[N];//标记该点是否为停靠点
int dist[N];//dist[i]表示i这个点级别最低是多少
int q[N], hh, tt = -1;//拓扑排序数组
int h[N], e[M], ne[M], w[M],idx;//邻接表数组
 
void add(int a, int b, int c)//邻接表模板
{
    d[b] ++ ;//b入度加1
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}
 
void topsort()//拓扑排序模板
{
    for (int i = 1; i <= n + m; i ++ )//要算上一个虚拟点
        if (!d[i]) q[++ tt] = i;
    
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0) q[++ tt] = j;
        }
    }
}
 
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        int cnt;
        scanf("%d", &cnt);
        memset(st, 0, sizeof st);
        int start = n, last = 1;//表示该车次从哪个车站开始到哪个车站结束
        
        while (cnt -- )
        {
            int stop;
            scanf("%d", &stop);
            st[stop] = true;//表示stop为停靠点
            start = min(start, stop);
            last = max(last, stop);
        }
        
        int ver = n + i;//在非停靠边和停靠边之间建立一个虚拟点
        for (int j = start; j <= last; j ++ )//从start开始到last结束
            if (st[j]) add(ver, j, 1);
            else add(j, ver, 0);
    }
    
    topsort();
    
    for (int i = 1; i <= n; i ++ ) dist[i] = 1;//每个车站级别最低为1，这里也可以建立一个虚拟源点，虚拟源点到每个点的权值为1
    for (int i = 0; i < n + m; i ++ )//加上虚拟源点
    {
        int j = q[i];
        for (int k = h[j]; k != -1; k = ne[k])
            dist[e[k]] = max(dist[e[k]], dist[j] + w[k]);//求最小的级别要用最长路，这里和差分约束的思想一样
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);//找出所有符合条件的级别中最大的那个
    
    cout << res << endl;
    
    return 0;
}

 若不了解这句话(dist[e[k]] = max(dist[e[k]], dist[j] + w[k]);)的同学可以看看差分约束的思想：

(1条消息) 《图论：差分约束算法详解 + 算法证明》+ 模板题：糖果_wsh1931的博客-CSDN博客