P1566 确定比赛名次 - 题解

登录注册上岸

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

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

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

2025年3月25日 20:28

确定比赛名次题解：

P1566

回复 0 | 赞 3 | 浏览 241

#include<stdio.h> #include<vector> #include<queue> using namespace std; int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ if(n==0){ &...

2025年3月11日 23:52

P1566 确定比赛名次答疑提问：求助，不知道哪点有问题

P1566

回复 2 | 赞 8 | 浏览 583

#include using namespace std; struct TNode { int data; TNode* rchild, * lchild; }; void Insert(TNode*& root, int x) { if (!root) { root = new TNode; &...

2025年2月23日 15:35

P1566 确定比赛名次答疑提问：

P1566

回复 2 | 赞 10 | 浏览 625

#include<bits/stdc++.h> using namespace std; const int maxn = 1000; int gmap[maxn][maxn]; //邻接矩阵存储 int indegree[maxn];//入度 void topo(int n){ priority_queue<int,vector<int>,greater<int> > q; int cnt; for(int i = 1;i<=n;i++){ if(indegree[i]...

2024年6月25日 16:43

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

P1566

回复 0 | 赞 0 | 浏览 792

//#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 | 赞 22 | 浏览 2.1k

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

2021年3月3日 12:58

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

P1566

回复 0 | 赞 1 | 浏览 11.8k

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

2021年2月27日 21:55

P1566

回复 0 | 赞 2 | 浏览 7.7k

输入的时候记得判断

2021年2月25日 14:45

P1566

回复 0 | 赞 1 | 浏览 9.6k

#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 | 赞 7 | 浏览 10.3k

#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.8k

#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())...

1
2

题目确定比赛名次

题解数量11

发布题解在线答疑

热门题解

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

2 P1566 确定比赛名次答疑提问：

3 P1566 确定比赛名次答疑提问：求助，不知道哪点有问题

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

5 拓扑排序的签到题

6 确定比赛名次题解：

7 重复数据

8 拓扑排序

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

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