hdu 1285 确定比赛名次 拓扑排序 字典序最小解

缘起

日常浪费生命 hdu 1285 确定比赛名次

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛
队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用
P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input
输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数
据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output
给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数
据确保一定能有一个符合要求的排名。

Sample Input
4 3
1 2
2 3
4 3

Sample Output
1 2 4 3

红果果的拓扑排序啊~ 直接板子伺候,唯一需要注意的是, 要求输出字典序最小的解, 所以只需要保证优先开拓栈中较小的点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,m, indeg[505], ans[505], top,s[505], tops; // s和ans是拓扑排序中的2个栈,这里为了排序方便, 就不再使用栈的stl了
vector<int> g[505];
typedef vector<int>::iterator vit;

bool cmp(int &a, int &b)
{
	return a>b;
}

void topsort()
{
	top = tops = 0;
	for (int i = 1; i<=n;i++)
	{
		if (!indeg[i])
		{
			s[tops++] = i;
		}
	}
	while(tops)
	{
		sort(s,s+tops, cmp); // 唯一和普通拓扑排序不同的地方:降序排序,保证输出字典序最小解
		int tt = s[--tops];
		ans[top++] = tt;
		for (vit x = g[tt].begin(); x!=g[tt].end(); x++)
		{
			if (!--indeg[*x])
			{
				s[tops++] = *x;
			}
		}
	}
	for (int i = 0; i<top; i++)
	{
		if (i)
		{
			putchar(' ');
		}
		printf("%d", ans[i]);
	}
	puts("");
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d", &n,&m))
	{
		memset(indeg, 0, sizeof(indeg));
		for (int i = 1; i<=n; i++)
		{
			g[i].clear();
		}
		while(m--)
		{
			int a,b;
			scanf("%d%d", &a, &b);
			g[a].push_back(b);
			indeg[b]++;
		}
		topsort();
	}
	return 0;
}

ac情况

Status Accepted
Time 93ms
Memory 1312kB
Length 1130
Lang G++
Submitted 2019-09-08 07:46:24
Shared
RemoteRunId 30529028

但是总让人不爽的事情是上面直接sort太暴力了!!! 可不可以每次优雅的决定栈s中下一个需要开拓的节点呢? 这个节点有什么特征? emmm, 顶点标号最小! 那还有啥好说的~ 优先队列直接上啊~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
//#define LOCAL

int n,m, indeg[505], ans[505], top, head[505], cnt;
priority_queue<int, vector<int>, greater<int> > s; // 将传统拓扑排序中的栈换成了优先队列(小根堆)

struct Arc
{
	int from, to, nxt;
}g[2505];

void addArc(int a, int b)
{
	g[cnt].from = a, g[cnt].to = b, g[cnt].nxt = head[a];
	head[a] = cnt++;
}

void topsort()
{
	top = 0;
	for (int i = 1; i<=n;i++)
	{
		if (!indeg[i])
		{
			s.push(i);
		}
	}
	while(!s.empty())
	{
		int tt = s.top();
		s.pop();
		ans[top++] = tt;
		for (int h = head[tt],to;~h;h = g[h].nxt)
		{
			to = g[h].to;
			if (!--indeg[to])
			{
				s.push(to);
			}
		}
	}
	for (int i = 0; i<top; i++)
	{
		if (i)
		{
			putchar(' ');
		}
		printf("%d", ans[i]);
	}
	puts("");
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d", &n,&m))
	{
		memset(indeg, 0, sizeof(indeg));
		memset(head, -1, sizeof(head));
		cnt = 0;
		while(m--)
		{
			int a,b;
			scanf("%d%d", &a, &b);
			addArc(a,b);
			indeg[b]++;
		}
		topsort();
	}
	return 0;
}

ac情况（既优雅 又快速——从93ms优化到了15ms, 而且在经典拓扑排序基础上改动甚少）

Status Accepted
Time 15ms
Memory 1276kB
Length 1154
Lang G++
Submitted 2019-09-08 07:57:36
Shared
RemoteRunId 30529031

所以不能只会套板子~ 还要理解板子的思想，这是普通 ACMer和优秀ACMer的重大区别之一（还有一个区别是女装大佬? ehhhh）