首页 > 代码库 > hdu1285 拓扑排序+优先队列
hdu1285 拓扑排序+优先队列
原题地址
这算是我个人AC的第一个拓扑排序题目吧。
题目解读
给出几组比赛的胜负情况。判断最后的排名。根据题意这就是一个明显的拓扑排序问题了。
注意
- 如果因为可能的排名有多种情况,这时要保证编号小的在前。
- 题目输入的数据可能有重复边
拓扑排序
首先统计每个结点的入度。将度为0的结点编号放入队列(此题放入优先队列中)中。
然后进行循环:
- 取出队头结点,视作边的起点。
- 然后“删除与该点相连的边”,代码就是将这个图中的该边另一个结点(即终点)的入度减一;
- 如果减一以后,终点的入度变为了0,那么将终点的编号入队列。
- 判断队列是否为空,若不空,则回到1
优先队列
C++ STL中有优先队列的类——priority_queue<T>。默认优先队列是值越大,优先级越高。所以比如priority_queue<int> q。这里面的元素是降序排列的。如果我们要实现升序需要重载。
priority_queue<int,vector<int>,greater<int> > q;>>有个有意思的问题是我并没有加vector的头文件,但这样声明一个队列,却并不报错。看来我对STL底层还是了解不深。。
代码
#include<iostream> #include<queue> #include<cstdio> #include<cstring> using namespace std; bool map[501][501]; int in[501]; priority_queue<int,vector<int>,greater<int> > q; void topo(int n) { for(int i=1;i<=n;i++) { if(in[i]==0) q.push(i); } int c=1; while(!q.empty()) { int v=q.top(); q.pop(); if(c!=n) { cout<<v<<" "; c++; } else cout<<v<<endl; for(int i=1;i<=n;i++) { if(!map[v][i]) continue; in[i]--; if(!in[i]) q.push(i); } } } int main() { int n,m,i,j; while(cin>>n>>m) { int k=0; memset(map,0,sizeof map); memset(in,0,sizeof in); while(m--) { cin>>i>>j; if(map[i][j]) continue; map[i][j]=1; in[j]++; } topo(n); } }
hdu1285 拓扑排序+优先队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。