Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

绿色网站无广告
会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

HDOJ 1285:确定比赛名次 拓扑排序

来源: bruce128 分享至:

   这道题的关键是拓扑排序,但是同时入度为0的结点可能有多个结点,按题目要求,用优先级队列便可解决。另外,不要忘记判断重边。

   我的AC代码。

   昨天晚上想到判断重边的工作完全可以交给STL的find()函数来做,自己没必要写函数,于是修改了一下。现在整个程序更加简洁了。

  

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;

const int Max = 510;
vector<int> t[Max];
int indegree[Max];
 int main()
{
	priority_queue<int, vector<int>, greater<int> > q;
	vector<int> fin;
	int n, m, g, l;
	while(cin >> n >> m)
	{
		memset(indegree, 0, sizeof(indegree));

		for(int i=0; i<m; i++)
		{
			scanf("%d%d", &g, &l);
			if(find(t[g].begin(), t[g].end(), l) == t[g].end()) 
                        //判断重边
			{
				t[g].push_back(l);
				indegree[l] ++;
			}
		}

		for(int i=1; i<=n; i++)
			if(!indegree[i]) q.push(i);

		while(!q.empty())
		{
			int cur = q.top();
			q.pop();
			fin.push_back(cur);
			for(int i=0; i<t[cur].size(); i++)
			{
				int adj = t[cur][i];
				indegree[adj] --;
				if(!indegree[adj]) q.push(adj);
			}
		}

		for(int i=0; i<n; i++)
			if(i < n-1) printf("%d ", fin[i]);
			else printf("%d\n", fin[i]);

		while(!q.empty()) q.pop();
		fin.clear();
		for(int i=0; i<Max; i++) t[i].clear();
	}
	system("pause");
	return 0;
}



Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史