P1566 确定比赛名次 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年6月25日 16:43

我错的地方：写了init没调用

P1566

回复 0 | 赞 0 | 浏览 406

//#include <bits/stdc++.h> #include <iostream> #include <unordered_set> #include <queue> using namespace std; #define maxn 505 #define for_(i,a,b) \ for (int i = (a); i < (b); i++) unordered_set<int> G[maxn]; int in...

2023年9月11日 17:15

确定比赛名次题解：拓扑排序

P1566

回复 0 | 赞 0 | 浏览 1.2k

解题思路：拓扑排序裸题。所谓的拓扑排序就是将入度为0的节点编号入队（因题目要求输出编号小的队伍在前面，所以采用最小堆优先队列来维护条件），当队首元素出队时，依次以它为尾的弧的另一端节点入度减1，同样只要有节点的入度减完为0的就其入队，循环直至不存在无前驱的顶点。当然此题不存在有向环，因为自己不会和自己比赛，虽然输入有可能出现重复数据即相同的有向边，但是出队的元素已经将其容器中的每个元素编号（即邻接点）的入度都减1，最后有多组相同重复的数据（即邻接点）的入度会减为0，这时入队就不存在有和之前相同的编号，所以不必担心因重边（有向边）而出现输出有相同的顶点编号。 #inclu...

2021年3月3日 12:58

1566-确定比赛名次（Python实现）

P1566

回复 0 | 赞 1 | 浏览 11.0k

思路分析：本题的题意是根据每行输入的部分次序关系，从而还原整个比赛程序的次序关系。刻画问题时，可以将队编号用结点表示，对之间的次序关系用有向边表示，那么每行输入的P1，P2表示P1队赢了P2队，就可以表示为P1→P2。这样M行的输入数据实际上就是给出的M条有向边。这样问题的全局表示就刻画出来了，实际上是一张有向无环图。接下来确定全局次序关系的思路是，每一步扫描所有没有前驱结点的结点，这些结点是“候选第1名”，从中选取序号最小的，计入结果列表，它就是全局第1名,然后将此结点从图中删除，并把该结点发出的所有边删除。重复此过程直至所有边删除完毕，最后剩余的...

2021年2月27日 21:55

P1566

回复 0 | 赞 1 | 浏览 7.2k

输入的时候记得判断

2021年2月25日 14:45

P1566

回复 0 | 赞 0 | 浏览 9.1k

#include <bits/stdc++.h> using namespace std; const int N = 510; int n, m; vector<int> e[N]; vector<int> ans; int d[N];//记录入度 bool topsort() { priority_queue<int, vector<int>, greater<int>> q; for(int i = 1; i <= n; i++) if(!d[i]) q...

2021年2月20日 10:13

拓扑排序注意可能有重复数据

P1566

回复 0 | 赞 0 | 浏览 9.8k

#include <iostream> #include <string.h> #include <queue> using namespace std; const int maxn=505; int g[maxn][maxn]; int indegree[maxn]; int ans[maxn]; int n,m,idx; priority_queue<int, vector<int>, greater<int> > q; void tops...

2021年1月26日 17:22

打卡

P1566

回复 0 | 赞 0 | 浏览 7.3k

#include <bits/stdc++.h> using namespace std; const int maxn=505; int len[maxn]; vector<int>a[maxn]; priority_queue <int ,vector<int>,greater<int>>q; void topo(int n) { for(int i=1;i<=n;i++) if(!len[i])q.push(i); int flag=0; while(!q.empty())...

2020年3月11日 15:43

拓扑排序的签到题

P1566

回复 1 | 赞 0 | 浏览 13.0k

#include<bits/stdc++.h> using namespace std; int const MAXN=501; vector<vector<int> > graph(MAXN); int degree[MAXN]={0}; vector<int> Topo(int n){ priority_queue<int,vector<int> ,greater<int> > node; vector<int> ans; for(i...

题目确定比赛名次

题解数量8

热门题解

1 重复数据

2 1566-确定比赛名次（Python实现）

3 拓扑排序

4 我错的地方：写了init没调用

5 打卡

6 拓扑排序的签到题

7 确定比赛名次题解：拓扑排序

8 拓扑排序注意可能有重复数据