[蓝桥杯][算法提高VIP]士兵排队问题

说在前面，这题没标明要“对于位置多种选择的字母尽量保证按字典序排序”

更新于2022.4.3

上面说的也不是很对，比如样例，显然ABFD是字典序更小的合法方案，但是答案却要求输出AFBD，这样上面的说法也就不合理了（自己否定原来的自己）

下面的AC代码对于我下面图中给出的“是拓扑”中的最后一个样例的测试输出始终不是ABCDE，也就是说并不是输出的字典序最小的，反正确实AC了，只能说这道题当个笑话看看吧。至于如果要按照字典序最小的方式输出的话，我最下面补充了一段代码。

题目

题目链接

题解

拓扑排序。

太坑了，你要是用的模板是入度自减为零后直接入队的，那么你是最多过64%的数据； 经过我严密的测试，发现必须满足“那些位置不固定的字母，要尽量按字典序排列”，也就是由同一个结点扩展出来的入度自减后变为零的结点，ASCII码小的要先入队才行。这点是题目没提到的。 所以，如果广大同学搜到本篇博客算你走运，我找了一小时题解，没有一篇研究过，都是没法AC的代码，只有此链接下网站内的一篇题解AC了，仔细研究了仨小时后得出结论，蓝桥杯傻逼。更准确的说应该是这个网站傻逼，因为网上搜到的虽然都没有AC，但是他们应该是在蓝桥官网上提交的，因此可以AC，但是这个网站不行。（用着人家免费的题，居然还骂人家，就骂这一次，下次一定不）

进入正题

什么是拓扑？ 看个图吧，看定义感觉理解的还是不会到位。 存在环了就不存在拓扑序了。存在先后关系，就存在拓扑序。

拓扑排序具有以下几点（个人总结所以比较没逻辑）：

1. 拓扑排序是广搜的应用
2. 拓扑排序是针对有向图来说，无向图没有拓扑序列
3. 有向无环图一定存在拓扑序列（有向无环图也被称作拓扑图）
4. 与入度有关
5. 入度为0的点作为拓扑序的起点
6. 一个图的拓扑序不一定唯一

拓扑模板：

将入度为0的点入队
while(队列不空) {
	取出队头t
	枚举队头t的所有出边（出边为t -> j）
		t的入度--（删除t -> j）
		判断t的入度是否为0，若为0则将t加入队列
}

代码模板：

// 先将入度为0的结点入队，同时保存在ans中
while(!q.empty()) {
		int t = q.front();
		q.pop();
		for(int i = h[t];i != -1;i = ne[i]) {
			int j = e[i];
			--d[j];
			if(!d[j]) q.push(j), ans[++sum] = j;
		}
	}
}
// 其实入队顺序（或者出队顺序）就是一个拓扑序

一般使用邻接表实现。

邻接表的相关内容自行百度吧，这里我只给出模板：

// N为点个数， M为边个数
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
	e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
// 遍历
// u表示编号为u的点
for(int i = h[u];i != -1;i = ne[i]) { // 其实遍历的是idx
	int v = e[i]; // u所连结点的编号	
	// ...
}
// 初始化
memset(h, -1, sizeof h);

邻接表是为每个点都开一个单链表，表示与每个点相连接的点有哪些。 idx为每条边的编号。 h[a]表示编号为a的点与其他点连边的编号。 e[idx]表示idx这条边终点编号。 ne[idx]表示idx这条边的下一条边的idx。

AC代码1（适合于知道优先队列的同学）

#include
using namespace std;
const int N = 30, M = 1010;

int e[M], ne[M], h[N], idx;
char s[N];
int only[N][N], vis[N], ans[N], in[N];
int sum, cnt;
queue q;
priority_queue pq; 

void add(int a, int b) {
	e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}

int main() {
	
	memset(h, -1, sizeof h);
	while(~scanf("%s", s)) {
		int a = s[0]-64, b = s[2]-64;// a:1  b:2  c:3  ……
		if(!only[a][b]) { // 用于防止一条边多次输入影响入度，好像给的数据并没有这样的，这只是以防万一
			add(a, b);
			in[b] ++; // 入度
			only[a][b] = 1;
			if(!vis[a]) cnt++, vis[a] = 1; // vis[i]表明字母i是不是要进行排队，即字母i是不是出现过
			if(!vis[b]) cnt++, vis[b] = 1;
		}
	}
	for(int i = 1;i