HDU 1285 确定比赛名次(拓扑排序&&优先队列优化)
拓扑排序最主要的就是依靠入度进行排序，至于入度是什么，这是一个传送门 点开看看就好了。以这道题为例，裁判不知道队伍的成绩，只知道胜负，自然获胜的越多就越靠前，那么我们需要开一个二维数组来记录谁打败了谁，代码中我用了w表示win，l表示lose，那么vis[w][l]就表示w打败了l，把这个标记为1，说明他们两个比过了，然后我们还需要一个数组来记录入度，既然l输了那么就让dep[l]++，表示l的入度+了1，然后我们按入度从小到大进行输出就好了，因为题目中说明了输入的数据确保是正确的且只有一种答案，所以我们就不需要考虑如果a赢了b，b赢了c，c赢了a等等其他的乱七八糟的情况了。大概思路就是这样，具体怎么实现看代码吧。
AC代码：
代码语言：javascript复制#include
#include
#include
using namespace std;
const int MAXN = 505;
bool vis[MAXN][MAXN]; // 用于标记谁打败了谁
int dep[MAXN]; // 存入度
int w,l; // win\lose
int n,m;
void TopoSort(int n){
int flag;
for(int i=1;i<=n;i++){ // 因为编号为1-n
for(int j=1;j<=n;j++){
if(dep[j] == 0){ // 找到入度为0的点
printf("%d%c",j,i == n? '\n' : ' '); // 输出
flag = j; // 标记这个点
dep[j]--; // 将其入度-1
break; // 跳出循环进入下一个循环
}
}
for(int j=1;j<=n;j++){ // 寻找被flag打败的点
if(vis[flag][j]){ // 如果flag把j打败了
vis[flag][j] = false; // 标记找到过
dep[j]--; // j入度-1
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m)){
memset(vis,0,sizeof(vis)); // 初始化
memset(dep,0,sizeof(dep));
for(int i=0;i scanf("%d%d",&w,&l); if(!vis[w][l]){ // 查重 vis[w][l] = true; // 标记w赢了l dep[l]++; // 失败者l的入度+1 } } TopoSort(n); } return 0; } /*** [来源] HDU 1285 [题目] 确定比赛名次 [思路] 拓扑排序基础题 [输入] 4 3 1 2 2 3 4 3 [输出] 1 2 4 3 */ 这样写时间复杂度会有点高，所以我们可以对拓扑排序用优先队列进行优化。 AC代码： 代码语言：javascript复制#include #include #include #include using namespace std; const int MAXN = 505; bool vis[MAXN][MAXN]; // 用于标记谁打败了谁 int dep[MAXN]; // 存入度 int w,l; // win\lose int n,m; priority_queue void TopoSort(int n){ for(int i=1;i<=n;i++){ // 遍历 入度为0的入队 if(dep[i]==0){ q.push(i); } } int temp = 1; // 标记输出结果后面是否输出空格 while(!q.empty()){ int ans = q.top(); q.pop(); if(temp != n){printf("%d ",ans);temp++;} else printf("%d\n",ans); for(int i=1;i<=n;i++){ // 找被ans打败的点 if(vis[ans][i]){ if(--dep[i]==0){ // 找到后先将其入度-1 如果-1后入度为0将其入队 q.push(i); } } } } } int main() { while(~scanf("%d%d",&n,&m)){ memset(vis,0,sizeof(vis)); memset(dep,0,sizeof(dep)); for(int i=0;i scanf("%d%d",&w,&l); if(!vis[w][l]){ vis[w][l] = true; dep[l]++; } } TopoSort(n); } return 0; }
