pingfan443

用户名：liu971294083

访问量：32792

签　名：

楼上的别敲了，我跟不上

等　　级
排　　名	130
经　　验	7642
参赛次数	6
文章发表	51
年　　龄	21
在职情况	学生
学　　校	b站
专　　业	软件开发

　　自我简介：

搁劲学

TA的其他文章

[编程入门]结构体之成绩统计2-题解(C语言代码)
浏览：630

[编程入门]筛选N以内的素数-题解(C语言代码)
浏览：337

二级C语言-计算素数和-题解(C语言代码)
浏览：2801

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯算法提高VIP-士兵排队问题（C++代码）

　　作者: pingfan443　　　　发表时间：2020-01-31 20:21:22 浏览：1310　|　评论：0　

原题链接：蓝桥杯算法提高VIP-士兵排队问题

思路：拓扑排序
1. 在有向图中选一个没有前驱的顶点且输出
1. 从图中删除该顶点和所有以它为尾的弧
重复上述步骤，直至全部顶点已输出，若存在有前驱的节点没输出完，那么就有环。
直接模拟上述步骤：
**思路1**:参考思路：[传送门](https://blog.csdn.net/weixin_42765557/article/details/88599824 "传送门")
`````cpp
#include<cstdio>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
int main()
{
	//freopen("test9.in","r",stdin);
	int station[26];//保存在本次排队中的点 
	char str[3];
	set<int>str_out[26];//记录出度 
	set<int>str_in[26];//记录入度为0的点同时保存点的边信息 
	memset(station,0,sizeof(station));
	while(scanf("%s",str)!=EOF)
	{
		str_out[str[0]-'A'].insert(str[2]-'A');
		str_in[str[2]-'A'].insert(str[0]-'A');//这个在后边用于找入度为0的点和存储边信息
		station[str[0]-'A']=1;//记录排队的人，用于找入度为0的点
		station[str[2]-'A']=1; 
		
	}
		queue<int>p;
		int ans[26],k=0;//记录排队顺序 
		for(int i=0;i<26;i++)
		{
			if(str_in[i].size()==0&&station[i])//两者缺一不可 
			p.push(i);//入度为0的入队 
		}
		while(!p.empty()) 
		{
			int j=p.front();
			for(set<int>::iterator it=str_out[j].begin();it!=str_out[j].end();it++)
			{
				int t=*it;
				str_in[t].erase(j);//删除t点的所有出边
				if(str_in[t].size()==0)
				p.push(t);//将t点入队（因为他已经是入度为0的点） 
				
			}
			str_out[j].clear();//删除j点的所有出边 
			ans[k++]='A'+j;
			p.pop(); 
		}
		int i;
		for( i=0;i<26;i++)
		if(str_in[i].size()>0)//有环存在
		break;
		if(i==26)
		{
			for(int j=0;j<k;j++)
			printf("%c",ans[j]);
		}
		else
		printf("No  Answer!\n");
	return 0;
 } 
`````
总结：上述代码存在段错误（具体原因还没找出来）
~~待更~~
补：
思路2：参考思路：[传送门](https://blog.csdn.net/caipengbenren/article/details/88709227 "传送门")
重新换了一种思路，回来补这道题，结果还是没有AC，错误50%，经过研究发现自己有一部分数据确实通不过去，就像数据有的给重了（A>B出现两次）我这个代码就过不去了，我也用set+pair判重了(代码在思路3)，还是跟答案不一样，但是我的思路1通过了以上我所测的所有数据，但是结果是运行错误27%。
```cpp
	#include<cstdio>
	#include<cstring>
	#include<vector>
	#include<queue>
	using namespace std;
	vector<int>edge[200];//存边 
	int in[200];
	void top_sort()
	{
	int count=0;
	queue<int>p;
	vector<int>ans;
	for(int i=0;i<200;i++)
	{
		if(in[i]==0)
		p.push(i);
		if(in[i]!=-1)
		count++;
	}
	while(!p.empty())
	{
		int head=p.front();
		p.pop();
		ans.push_back(head);
		for(int i=0;i<edge[head].size();i++)
		{
			int t=edge[head][i];
			in[t]--;
			if(in[t]==0)
			p.push(t);
		}
	}
	if(ans.size()==count)
	{
		for(int i=0;i<ans.size();i++)
		printf("%c",ans[i]);
	}
	else
	printf("No  Answer!\n");
}
int main()
{
	//freopen("test5.in","r",stdin);
	char a,b;
	memset(in,-1,sizeof(in));
	while(scanf("%c>%c",&a,&b)!=EOF)
	{
		getchar();//有了这个错误50%没有这个直接错误 
		edge[a].push_back(b);
		if(in[a]==-1)//-1（没有队员排队）0（入度为0）>0入度增加 
		{
			in[a]=0;
		}
		if(in[b]==-1)
		{
			in[b]=0;
		}
		in[b]++;
	}
	top_sort();
	return 0;
}
```
**思路3**：

#include<cstdio>
		#include<cstring>
		#include<vector>
		#include<queue>
		#include<utility>
		#include<set>
		using namespace std;
		vector<int>edge[200];//存边 
		int in[200];

set<pair<char,char>>vis;
		void top_sort()
		{
			int count=0;
			queue<int>p;
			vector<int>ans;
			for(int i=0;i<200;i++)
			{
				if(in[i]==0)
				p.push(i);
				if(in[i]!=-1)
				count++;
			}
			while(!p.empty())
			{
				int head=p.front();
				p.pop();
				ans.push_back(head);
				for(int i=0;i<edge[head].size();i++)
				{
					int t=edge[head][i];
					in[t]--;
					if(in[t]==0)
					p.push(t);
				}
			}
			if(ans.size()==count)
			{
				for(int i=0;i<ans.size();i++)
				printf("%c",ans[i]);
			}
			else
			printf("No  Answer!\n");
		}
		int main()
		{
			//freopen("test5.in","r",stdin);
			char a,b;
			memset(in,-1,sizeof(in));
			while(scanf("%c>%c",&a,&b)!=EOF)
			{
				getchar();//有了这个错误50%没有这个直接错误 （吃掉换行） 
				if(!vis.count(make_pair(a,b)))//避免重复（还是不行） 
				{
					vis.insert(make_pair(a,b));

edge[a].push_back(b);
						if(in[a]==-1)//-1（没有队员排队）0（入度为0）>0入度增加 
						{
							in[a]=0;
						}
						if(in[b]==-1)
						{
							in[b]=0;
						}
						in[b]++;

}
			}
			top_sort();
			return 0;
		}
总结：以上没有详写思路可以通过传送门看他们的思路，我是借鉴过来（由于篇幅太长，就写到这吧）遗憾的一道题=^=！
另外在博客上有两组数据供大家测试：[传送门](https://blog.csdn.net/qq_43566782/article/details/104129727 "传送门")

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

pingfan443

TA的其他文章

你可能喜欢

C语言训练-8除不尽的数（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

蓝桥杯算法提高VIP-士兵排队问题（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

时间转换（Java代码）

WU-复数求和（C++代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C二级辅导-公约公倍（C语言代码）

剪刀石头布（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

pingfan443

TA的其他文章

你可能喜欢

C语言训练-8除不尽的数 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

蓝桥杯算法提高VIP-士兵排队问题 （C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

时间转换 （Java代码）

WU-复数求和 （C++代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

剪刀石头布 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言训练-8除不尽的数（C语言代码）

蓝桥杯算法提高VIP-士兵排队问题（C++代码）

　　评论区

时间转换（Java代码）

WU-复数求和（C++代码）

C二级辅导-公约公倍（C语言代码）

剪刀石头布（C语言代码）