精华内容
下载资源
问答
  • 确定比赛名次

    2017-09-25 16:13:40
    题目网址:确定比赛名次

    题目网址:确定比赛名次

    这一题就是典型的拓扑排序的题目:输出比赛排名,但是有一点要求,符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。那么不能在使用常规的queue来实现,而必须采用priority_queue<int,vector<int>,greater<int> >q;这个是一个小顶堆,每次弹出堆中最小的元素。(这里顺便提一下大顶堆priority_queue<int> q;每次取出的元素是堆中最大的元素!)

    #include<iostream>
    #include<queue>
    #include<functional>
    #include<vector>
    using namespace std;
    priority_queue<int, vector<int>, greater<int> >q;
    vector<int> edge[600];
    int main()
    {
    	int n, m;
    	while (cin >> n >> m)
    	{
    		int *indegree = new int[n+1];
    		for (int i = 1; i <= n; i++)
    		{
    			edge[i].clear();
    			indegree[i] = 0;
    		}
    		for (int i = 0; i < m; i++)
    		{
    			int a, b;
    			cin >> a >> b;
    			indegree[b]++;
    			edge[a].push_back(b);
    		}
    		while (q.empty() == false)
    			q.pop();
    		for (int i = 1; i <= n ; i++)
    		{
    			if (indegree[i] == 0)
    				q.push(i);
    		}
    		int cnt = 0;
    		//int *ans = new int[n];
    		while (!q.empty())
    		{
    			int now = q.top();
    			q.pop();
    			//ans[cnt++] = now;
    			cnt++;
    			if (cnt == n)
    				cout << now << endl;
    			else
    				cout << now << " ";
    			for (int j = 0; j < edge[now].size(); j++)
    			{
    				indegree[edge[now][j]]--;
    				if (indegree[edge[now][j]]==0)
    					q.push(edge[now][j]);
    			}
    		}
    		/*for (int i = 0; i < n; i++)
    		{
    			if (i != n - 1)
    				cout << ans[i] << " ";
    			else
    				cout << ans[i] << endl;
    		}*/
    	}
    	return 0;
    }


    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,619
精华内容 647
关键字:

确定比赛名次