3.11 拓扑排序

来自版块：酒馆

文章发表：04-29 最后编辑：08-07

来自合集：算法提高课

251.家谱树

题目:

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的孩子的信息。

输出一个序列，使得每个人的孩子都比那个人后列出。

输入格式

第1行一个整数n，表示家族的人数；

接下来n行，第i行描述第i个人的孩子；每行最后是0表示描述完毕。

每个人的编号从1到n。

输出格式

输出一个序列，使得每个人的孩子都比那个人后列出；如果有多解输出任意一解。

数据范围

1≤n≤100

思路:

1.对于一个有向图来说，如果我们给它排一个序，对于每一条边来说，它都是由前面指向后面，那么它就是一个拓扑排序。拓扑图等价于有向无环图。

对于拓扑排序，首先我们统计每个点的入度，把入度为0的点入队。然后进行宽度优先搜索，当队列不空，每次取出队头t，遍历t的所有出边t→j，然后--d[j]，如果d[j]等于0了，那么就没有其他节点指向这个点了，就可以把j加入队列里。

2.把每一个人都看成一个结点，如果说一个结点的儿子是另一个结点，那么从父亲向儿子连接一条有向边。所以本质上是求一个拓扑排序的序列。

代码(c++):

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 110, M = N * N / 2;

int n;

int h[N], e[M], ne[M], idx;

int q[N];

int d[N]; //入度

void add (int a, int b)

{

e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;

}

void topsort()

{

int hh = 0, tt = -1;

for (int i = 1; i <= n; i ++ )

if (!d[i]) //入度为0

q[ ++ tt] = i;

while (hh <= tt)

{

int t = q[hh ++ ];

for (int i = h[t]; ~i; i = ne[i])

{

int j = e[i];

if ( -- d[j] == 0)

q[ ++ tt] = j;

}

int main()

{

cin >> n;

memset(h, -1, sizeof h);

for (int i = 1; i <= n; i ++ )

{

int son;

while (cin >> son, son)

{

add(i, son);

d[son] ++ ;

}

topsort();

for (int i = 0; i < n; i ++ ) printf("%d ", q[i]); //队列里的顺序就是拓扑排序的顺序

return 0;

}

252.奖金

题目:

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。

公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。

每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高!”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元，且必须是整数。

输入格式

第一行包含整数 n, m，分别表示公司内员工数以及参会代表数。

接下来m行，每行2个整数 a, b，表示某个代表认为第a号员工奖金应该比第b号员工高。

输出格式

若无法找到合理方案，则输出"Poor Xed";否则输出一个数表示最少总奖金。

数据范围

1≤n≤10000

1≤m≤20000

思路:

1.等价于差分约束的简化版。对于差分约束，时间复杂度比较高。如果所有边权都是正数，我们可以用强连通分量Tarjan的方法求解。

而本题，所有边权都是1，求最小值，就是求图的最长路。a≥b+1，从b向a连一个权为1的边。

此时我们可以直接用更简单的方法，因为边权为正的，所以如果它存在环，那么必然是无解的。

以求最长路为例子

①差分约束，求最长路。边权无限制，只能用spfa做。O(nm)。

②如果说所有边权非负，那么可以用Tarjan算法做。O(n+m)。

③如果所有边权＞0，那么可以用拓扑排序。O(n+m)。判是否有环即可。

2.对于奖金至少为100，我们可以建立一个虚拟原点，连接一个权为100的边。当然并不需要一定建出来，可以把初始dist赋值为100。

代码(c++):

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 10010, M = 20010;

int n, m;

int h[N], e[M], ne[M], idx;

int q[N];

int d[N];

int dist[N];

void add(int a, int b)

{

e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;

}

bool topsort()

{

int hh = 0, tt = -1;

for (int i = 1; i <= n; i ++ )

if (!d[i])

q[ ++ tt] = i;

while (hh <= tt)

{

int t = q[hh ++ ];

for (int i = h[t]; ~i; i = ne[i])

{

int j = e[i];

if ( -- d[j] == 0)

q[ ++ tt] = j;

}

return tt == n - 1;

}

int main()

{

scanf("%d%d", &n, &m);

memset(h, -1, sizeof h);

while (m -- )

{

int a, b;

scanf("%d%d", &a, &b);

add(b, a);

d[a] ++ ;

}

if (!topsort()) puts("Poor Xed");

else

{

for (int i = 1; i <= n; i ++ ) dist[i] = 100;

for (int i = 0; i < n; i ++ )

{

int j = q[i];

for (int k = h[j]; ~k; k = ne[k])

dist[e[k]] = max(dist[e[k]], dist[j] + 1);

}

int res = 0;

for (int i = 1; i <= n; i ++ ) res += dist[i];

printf("%d\n", res);

}

return 0;

}

253.可达性统计

题目:

给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

输入格式

第一行两个整数 N, M，接下来M行每行两个整数x，y，表示从x到y的一条有向边。

输出格式

输出共N行，表示每个点能够到达的点的数量。

数据范围

1≤N, M≤30000

思路:

1.因为它是一个有向无环图，所以我们可以对它进行DP。对于当前这个点来说，假设i可以到很多点，假设我们第一个点能到j1，第二个点能到j2……jk。假设f(i)是所有能从i到达的点的集合。那么f(i)＝{i}∪f(j1)∪……∪f(jk)。所以用拓扑排序的逆序一定可以保证在求i的时候f(j1)……已经被求好了。集合怎么表示呢？我们可以用长度为n的二进制串来表示，为0就表示不能到这个点，1就表示能到。这个串我们用布尔数组存比较慢，使用bitset存并且用或运算即可。

代码(c++):

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <bitset>

using namespace std;

const int N = 30010, M = 30010;

int n, m;

int h[N], e[M], ne[M], idx;

int d[N], q[N];

bitset<N> f[N]; //每个点可以到的点的集合，<>里的N表示bitset的长度，也就是位数

void add(int a, int b)

{

e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;

}

void topsort()

{

int hh = 0, tt = -1;

for (int i = 1; i <= n; i ++ )

if (!d[i])

q[ ++ tt] = i;

while (hh <= tt)

{

int t = q[hh ++ ];

for (int i = h[t]; ~i; i = ne[i])

{

int j = e[i];

if ( -- d[j] == 0)

q[ ++ tt] = j;

}

int main()

{

scanf("%d%d", &n, &m);

memset(h, -1, sizeof h);

for (int i = 0; i < m; i ++ )

{

int a, b;

scanf("%d%d", &a, &b);

add(a, b);

d[b] ++ ;

}

topsort();

for (int i = n - 1; i >= 0; i -- ) //按拓扑排序的倒序来求，保证每个点在求的时候所需要的集合都被算出来

{

int j = q[i];

f[j][j] = 1; //j能到自己

for (int k = h[j]; ~k; k = ne[k]) //遍历邻边

f[j] |= f[e[k]];

}

for (int i = 1; i <= n; i ++ ) printf("%d\n", f[i].count()); //bitset的api，count里不加参数是返回的1的个数，加参数返回的是参数的个数，参数可以是0或1

return 0;

}

254.车站分级

题目:

一条单向的铁路线上，依次有编号为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

思路:

1.如果我们给它这个区间里的车站的等级排个序。所有停靠站点的级别最小值就是临界点，那么区间内所有级别大于等于这个车站的都要停，小于必须全不停。

假设6个车站。走了1356这几个车站，那么站点最小级别一定严格大于2,4的等级。如果1号车站等级＞2号车站等级，那么从2到1连一条边。那么这个图里一定是没有环的。所以就和251题类似，从b向a连一条权为1边。但是如果按这个思路来建边，我们每个车站最多会建500*(1000-500)=250000条边，又因为最多1000个车站，所以最多可能2.5*10⁸条边。显然不太可行。所以要优化一下这个题。

2.对于从左边的集合(n个点)指向右边的集合(m个点)的许多边，我们可以在两个集合中建立一个虚拟点，让左边的点连中间的虚拟点，虚拟点再连向右边的集合，那么就从n×m变成了n+m。假设左边的车站的等级严格小于右边的车站等级，那么我们可以让左边的点向虚拟点连接一条权为0的边，从虚拟点向右边的集合里的点连接一条权为1的边。其中，这里一条边a→b，权为w，代表b至少比a多w。所以这种建图方式就等价于之前的建图方式。

代码(c++):

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 2010, M = 1000010; //由于有虚拟原点，所以点数为2000。边数是每个车最多1000条边，有1000趟车，所以就是一百万条边

int n, m;

int h[N], e[M], ne[M], w[M], idx;

int q[N], d[N];

int dist[N];

bool st[N];