HDU 1285 确定比赛名次(简单拓扑排序)
http://acm.hdu.edu.cn/showproblem.php?pid=1285
题意:给你N个点M条有向边,要求你输出字典序最小的拓扑排序序列.
分析:前面已经做过很多这种题了,没什么说的直接输出字典序最小的拓扑序列即可.
注意:非递归求字典序最小的拓扑序列需要用到优先队列,且要是小值优先的队列.大致的思想就是队列Q总是将当前在入度为0的最小节点优先取出.保证了字典序最小.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=500+10;
int n,m;
vector<int> G[maxn];
int in[maxn];
void topo()
{
priority_queue<int,vector<int>,greater<int> > Q; //保证小值int先出队列
int ans[maxn],cnt=0;
for(int i=1;i<=n;i++)if(in[i]==0) Q.push(i);
while(!Q.empty())
{
int u=Q.top(); Q.pop();
ans[cnt++]=u;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(--in[v]==0)
Q.push(v);
}
}
printf("%d",ans[0]);
for(int i=1;i<n;i++)
printf(" %d",ans[i]);
puts("");
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
memset(in,0,sizeof(in));
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
in[v]++;
}
topo();
}
return 0;
}
分享到:
相关推荐
算法-确定比赛名次(HDU-1285).rar
hdu杭电所有题目按照ac数量排序,python分析
hdu ACM 各种排序
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
http://acm.hdu.edu.cn/showproblem.php?pid=2020 绝对值排序 txt格式
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1005.比较简单的一道题,有兴趣的可以看看。
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码