题解【洛谷P1983】[NOIP2013]车站分级

题面

题解

不难想到拓扑排序

于是每一个等级高的向等级低的连一条边

考虑拓扑排序过程中的分层

对于每个点进行分层

于是答案就是这些点中的最大层数

然后就会RE

发现我们多连了一些重复的边

用一个标记数组记录两个点之间是否连边即可

代码

#include <bits/stdc++.h>

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

const int maxn = 1003;

int n, m, ans, g[maxn][maxn]/*输入数组*/;

int viss[maxn], b[maxn][maxn]/*标记是否连边*/, ceng[maxn]/*分层*/, in[maxn]/*统计入度*/;

vector <int> vv[maxn];//存图

inline void topsort()//拓扑排序

{

	queue <int> q;

	for (int i = 1; i <= n; i+=1) if (!in[i]) q.push(i), ceng[i] = 1;//初始化队列+分层

	while (!q.empty())

	{

		int u = q.front(); q.pop();

		int len = vv[u].size();

		for (int i = 0; i < len; i+=1)

		{

			int v = vv[u][i];

			if (!(--in[v])) ceng[v] = ceng[u] + 1/*分层*/, q.push(v);

		}

	}

	for (int i = 1; i <= n; i+=1) ans = max(ans, ceng[i]);//计算答案

}

int main()

{

	n = gi(), m = gi();

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

	{

		g[i][0] = gi();

		memset(viss, 0, sizeof(viss));//初始化

		for (int j = 1; j <= g[i][0]; j+=1)

		{

			g[i][j] = gi();

			viss[g[i][j]] = 1;//标记已经过该站点

		}

		for (int j = g[i][1]; j <= g[i][g[i][0]]; j+=1)

		{

			if (!viss[j])//没有经过该站点，说明该站点等级比经过的站点等级低

			{

				for (int k = 1; k <= g[i][0]; k+=1)

				{

					if (!b[j][g[i][k]])//没有边

					{

						vv[j].push_back(g[i][k]);//存图

						b[j][g[i][k]] = 1;//标记有边

						++in[g[i][k]];//统计入度

					}

				}

			}

		}

	}

	topsort();

	printf("%d\n", ans);//输出答案

	return 0;

}

巴特西

题解【洛谷P1983】[NOIP2013]车站分级

题解

代码

最新文章

热门文章