Hdu1285 step5.2.5 确定比赛名次

2024-04-02 17:08

本文主要是介绍Hdu1285 step5.2.5 确定比赛名次,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 260 AcceptedSubmission(s): 150

 

Problem Description

有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。

 

 

Input

输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。

 

 

Output

 

           给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。

 

其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。

 

 

Sample Input

4 3

1 2

2 3

4 3

 

 

Sample Output

1 2 4 3

 

 

Author

SmallBeer(CML)

 

 

Source

杭电ACM集训队训练赛(VII)

 

 

Recommend

lcy

 

题解:

拓扑排序的经典应用,需要一个二维数组保存队伍k的入度数(输给i队,为team[i][k]++),into[i]保存该队伍一共输的次数,当into[j]==0时,输出该队序号,然后所有a[i][j]>0的队伍,into[j]--;然后重复上面的过程。

 

源代码:

#include <iostream>

#include <math.h>

using namespace std;

 

int team[510][510];

int into[510];

 

bool topologicalsort(int n)

{

   memset(into,0,sizeof(into));

   for(int i = 1;i <= n; i++)

   {

     for(int j = 1;j <= n;j++)

     {

        if(team[i][j]> 0)

          into[j]++;

     }

   }

   into[0] = 1;

   intans = 0;

   for(int i = 1;i <= n;i++)

   {

     intj = 0;

     while(into[j]!= 0)

     {

        j++;

        if(j> n)

          returnfalse;

     }

     if(!ans++)

        printf("%d",j);

     else

        printf(" %d",j);

     into[j] = -1;

     for(int k = 1;k <= n;k++)

     {

        if(team[j][k]> 0)

          into[k]--;

     }

   }

   cout << endl;

   returntrue;

}

int main()

{

   intn,m;

 

   while(cin>> n >> m)

   {

     memset(team,0,sizeof(team));

     inta,b;

     for(int i = 0;i < m;i++)

     {

        cin >> a >> b;

        team[a][b]++;

     }

     topologicalsort(n);

   }

   return0;

}

 

这篇关于Hdu1285 step5.2.5 确定比赛名次的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/870567

相关文章

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而

日本某地发生了一件谋杀案,警察通过排查确定杀人凶手必为4个 嫌疑犯的一个。以下为4个嫌疑犯的供词。

日本某地发生了一件谋杀案,警察通过排查确定杀人凶手必为4个 嫌疑犯的一个。以下为4个嫌疑犯的供词。 A说:不是我。 B说:是C。 C说:是D。 D说:C在胡说 已知3个人说了真话,1个人说的是假话。 现在请根据这些信息,写一个程序来确定到底谁是凶手。  static void Main()         {             int killer = 0;             fo

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追

ACM比赛中如何加速c++的输入输出?如何使cin速度与scanf速度相当?什么是最快的输入输出方法?

在竞赛中,遇到大数据时,往往读文件成了程序运行速度的瓶颈,需要更快的读取方式。相信几乎所有的C++学习者都在cin机器缓慢的速度上栽过跟头,于是从此以后发誓不用cin读数据。还有人说Pascal的read语句的速度是C/C++中scanf比不上的,C++选手只能干着急。难道C++真的低Pascal一等吗?答案是不言而喻的。一个进阶的方法是把数据一下子读进来,然后再转化字符串,这种方法传说中

结合Python与GUI实现比赛预测与游戏数据分析

在现代软件开发中,用户界面设计和数据处理紧密结合,以提升用户体验和功能性。本篇博客将基于Python代码和相关数据分析进行讨论,尤其是如何通过PyQt5等图形界面库实现交互式功能。同时,我们将探讨如何通过嵌入式预测模型为用户提供赛果预测服务。 本文的主要内容包括: 基于PyQt5的图形用户界面设计。结合数据进行比赛预测。文件处理和数据分析流程。 1. PyQt5 图形用户界面设计

保研 比赛 利器: 用AI比赛助手降维打击数学建模

数学建模作为一个热门但又具有挑战性的赛道,在保研、学分加分、简历增色等方面具有独特优势。近年来,随着AI技术的发展,特别是像GPT-4模型的应用,数学建模的比赛变得不再那么“艰深”。通过利用AI比赛助手,不仅可以大大提升团队效率,还能有效提高比赛获奖几率。本文将详细介绍如何通过AI比赛助手完成数学建模比赛,并结合实例展示其强大功能。 一、AI比赛助手的引入 1. 什么是AI比赛助手? AI比

【压力测试】如何确定系统最大并发用户数?

一、明确测试目的与了解需求 明确测试目的:首先需要明确测试的目的,即为什么要确定系统的最大并发用户数。这通常与业务需求、系统预期的最大用户负载以及系统的稳定性要求相关。 了解业务需求:深入了解系统的业务特性,包括用户行为模式、业务高峰期的时间段、用户请求的复杂程度等。 二、进行基准测试 确定正常负载下的性能:在开始压力测试之前,进行基准测试以确定系统在正常负载下的性能表现。这有助

Kaggle刷比赛的利器,LR,LGBM,XGBoost,Keras

刷比赛利器,感谢分享的人。 摘要 最近打各种比赛,在这里分享一些General Model,稍微改改就能用的 环境: python 3.5.2 XGBoost调参大全: http://blog.csdn.net/han_xiaoyang/article/details/52665396 XGBoost 官方API: http://xgboost.readthedocs.io/en

【HDU】1285 确定比赛名次 拓扑排序

确定比赛名次 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10963    Accepted Submission(s): 4374 Problem Description 有N个比赛队(1<=N<=500),

Java 确定线程池中工作线程数的大小

以问答形式展开,会更有针对性: 1、工作线程是不是越多越好?      不是。a、服务器cpu核数有限,所以同时并发或者并行的线程数是有限的,所以1核cpu设置1000个线程是没有意义的。  b、线程切换也是有开销的。频繁切换线程会使性能降低。 2、调用sleep()函数的时候,县城是否会占用着CPU?     不占用,sleep()函数切换时会把cpu让出来。accept()阻塞和rec