hdu 1285 确定比赛名次拓扑排序模板题优先队列-白红宇

hdu 1285 确定比赛名次拓扑排序模板题优先队列

阅读量：4073 次

发布时间：2019-05-25

本文共 730 字，大约阅读时间需要 2 分钟。

因为近期比赛有很多图论，但我不会，所以从头开始学，除了bfs判断连通外，这是第一个重点吧，以后都会用到

拓扑排序主要解决的问题是比赛名次构建的有向无环图，若有环，则不存在拓扑排序；

主要是根据入度和队列来解决的；

若输出序编号小的排前边，则用优先队列；

代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=510;int n,m;int dis[maxn];vector
       
         G[maxn];int main(){     int i,j;    while(cin>>n>>m)    {        priority_queue

,greater

> s; memset(dis,0,sizeof(dis)); for(i=0;i<=n;i++) { G[i].clear(); } //queue

s; int u,v; int start=0; for(i=1; i<=m; i++) { cin>>u>>v; dis[v]++; G[u].push_back(v); } for(i=1;i<=n;i++) { if(dis[i]==0) { s.push(i); } } while(!s.empty()) { int p=s.top(); s.pop(); start++; if(start==1) { cout<

转载地址：http://bygji.baihongyu.com/

你可能感兴趣的文章

hdu 1011 Starship Troopers （树形背包dp）

查看>>

hdu 1561 The more, The Better (树形背包dp)

查看>>

【设计模式】学习笔记14：状态模式（State）

查看>>

poj 1976 A Mini Locomotive （dp 二维01背包)

查看>>

斯坦福大学机器学习——因子分析（Factor analysis）

查看>>