首页 > 代码库 > hdu-1285 确定比赛名次
hdu-1285 确定比赛名次
http://acm.hdu.edu.cn/showproblem.php?pid=1285
因为输入数据一定有解,并且要编号小的队伍在前,那么用优先队列存储结果集即可。
//拓扑排序关键在于需要维护一个入度为0的顶点的集合。(只出不入) #include<stdio.h> #include<string.h> #include<iostream> #include<queue> #define Max 510 using namespace std; struct ADJ { int v; int last; }; ADJ adj[Max*Max]; int cnt_edge;//边的数量 int node[Max]; //以x为起点的最后一条边的编号 int in[Max];//入度 int n,m; priority_queue<int,vector<int>,greater<int> >q;//题目要求编号小的队伍在前,所以用优先队列,从小到大排序 void add_edge(int x,int y) //队列模拟集合 { adj[cnt_edge].last=node[x]; adj[cnt_edge].v=y; //当前边的终点。 node[x]=cnt_edge; //以x为起点的最后一条边的编号 cnt_edge++; }//邻接表的建立 void clear() { cnt_edge=0; //边的数量从0开始 memset(in,0,sizeof(in)); //初始化入度为0 memset(node,-1,sizeof(node)); //初始化每个点编号为-1 while(!q.empty()) q.pop(); } void top_sort() { vector<int>vec; //保存结果集 int now,next,j; while(!q.empty()) { now=q.top(); vec.push_back(now); //从集合中取出一个点,将该顶点放入结果集当中, q.pop(); for(j=node[now];j!=-1;j=adj[j].last)//遍历邻接表,从当前顶点遍历与之相连的所有边 { next=adj[j].v; in[next]--; //入度减1,表示移除这条边 if(in[next]==0) q.push(next); //如果该顶点的入度在减去这条边之后为0,那么将这个顶点也放入结果集当中 } } for(j=0;j<vec.size();j++) { //输出结果集 if(j==0) printf("%d",vec[j]); else printf(" %d",vec[j]); } printf("\n"); } int main() { //freopen("b.txt","r",stdin); while(scanf("%d %d",&n,&m)==2) { clear(); int x,y; while(m--) { scanf("%d %d",&x,&y); add_edge(x,y); in[y]++; //x指向y的边,y的入度加1 } int i; for(i=1;i<=n;i++) if(in[i]==0) //把入度为0的点加入集合 q.push(i); top_sort(); } return 0; }
hdu-1285 确定比赛名次
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。