主站
DreamJudge
院校信息
专业题库
模拟考试
机试真题
专业课程
答疑区
兑换中心
登录
注册
上岸
以下题解仅供学习参考使用。
抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在N诺是严格禁止的。
N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。
weinijuan
2024年6月25日 16:43
我错的地方:写了init没调用
P1566
回复 0
|
赞 0
|
浏览 438
//#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...
snake
2023年9月11日 17:15
确定比赛名次 题解:拓扑排序
P1566
回复 0
|
赞 0
|
浏览 1.3k
解题思路:拓扑排序裸题。所谓的拓扑排序就是将入度为0的节点编号入队(因题目要求输出编号小的队伍在前面,所以采用最小堆优先队列来维护条件),当队首元素出队时,依次以它为尾的弧的另一端节点入度减1,同样只要有节点的入度减完为0的就其入队,循环直至不存在无前驱的顶点。 当然此题不存在有向环,因为自己不会和自己比赛,虽然输入有可能出现重复数据即相同的有向边,但是出队的元素已经将其容器中的每个元素编号(即邻接点)的入度都减1,最后有多组相同重复的数据(即邻接点)的入度会减为0,这时入队就不存在有和之前相同的编号,所以不必担心因重边(有向边)而出现输出有相同的顶点编号。 #inclu...
jialChen
2021年3月3日 12:58
1566-确定比赛名次(Python实现)
P1566
回复 0
|
赞 1
|
浏览 11.1k
思路分析: 本题的题意是根据每行输入的部分次序关系,从而还原整个比赛程序的次序关系。刻画问题时,可以将队编号用结点表示,对之间的次序关系用有向边表示,那么每行输入的P1,P2表示P1队赢了P2队,就可以表示为P1→P2。这样M行的输入数据实际上就是给出的M条有向边。这样问题的全局表示就刻画出来了,实际上是一张有向无环图。接下来确定全局次序关系的思路是,每一步扫描所有没有前驱结点的结点,这些结点是“候选第1名”,从中选取序号最小的,计入结果列表,它就是全局第1名,然后将此结点从图中删除,并把该结点发出的所有边删除。重复此过程直至所有边删除完毕,最后剩余的...
N诺子言
2021年2月27日 21:55
重复数据
P1566
回复 0
|
赞 1
|
浏览 7.2k
输入的时候记得判断
shmilyzsc
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...
James
2021年2月20日 10:13
拓扑排序 注意可能有重复数据
P1566
回复 0
|
赞 0
|
浏览 9.9k
#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.4k
#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())...
Ang
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
拓扑排序 注意可能有重复数据