| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 158 人关注过本帖
标题:请各位帮我看看这道题,谢谢!
只看楼主 加入收藏
Jason_
Rank: 2
来 自:浙江台州
等 级:论坛游民
帖 子:43
专家分:66
注 册:2019-7-14
结帖率:50%
  问题点数:0  回复次数:4   
请各位帮我看看这道题,谢谢!
题目描述
冬令营的N(1 <= N <= 100)个优秀营员最近参加了场程序设计竞赛:)。在赛场上,营员们按1..N依次编号。每个营员的编程能力不尽相同,并且没有哪两个营员的水平不相上下,也就是说,营员们的编程能力有明确的排名。
整个比赛被分成了若干轮,每一轮是两个指定编号的营员的对决。如果编号为A的营员的编程能力强于编号为B的营员(1 <= A <= N; 1 <= B <= N; A <> B),那么他们的对决中,编号为A的营员总是能胜出。
小明想知道营员们编程能力的具体排名,于是他找来了营员们所有M(1 <= M <= 4,500)轮比赛的结果,希望你能根据这些信息,推断出尽可能多的营员的编程能力排名。比赛结果保证不会自相矛盾。

输入
* 第1行: 2个用空格隔开的整数:N 和 M
* 第2..M+1行: 每行为2个用空格隔开的整数A、B,描述了参加某一轮比赛的营员的编号,以及结果(编号为A,即为每行的第一个数的营员为胜者)

输出
* 第1行: 输出1个整数,表示排名可以确定的营员的数目

样例输入
5 5
4 3
4 2
3 2
1 2
2 5

样例输出
2
搜索更多相关主题的帖子: 比赛 能力 编号 编程 排名 
2019-11-27 20:51
Jason_
Rank: 2
来 自:浙江台州
等 级:论坛游民
帖 子:43
专家分:66
注 册:2019-7-14
  得分:0 
回复 楼主 Jason_
请各位快点看看这题,要求赶快交。谢谢大家!
2019-11-28 21:13
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:334
帖 子:6926
专家分:40239
注 册:2011-1-18
  得分:0 
网上一搜一大堆

我们反而没法做,即使代码写出来了也没法知道它对不对,因为缺少验证数据。
2019-11-29 08:45
Jason_
Rank: 2
来 自:浙江台州
等 级:论坛游民
帖 子:43
专家分:66
注 册:2019-7-14
  得分:0 
程序代码:
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 205
#define inf 0x3f3f3f3f
int dis[N],w[N][N],n,m,x,y;
bool vis[N];
void dijstra()
{
    int i,j;
    for(i=0;i<n;i++)
    {
        dis[i]=w[x][i];
        vis[i]=0;
    }
    dis[x]=0;
    vis[x]=1;
    for(i=0;i<n;i++)
    {
       int mark,mindis=inf;
       for(j=0;j<n;j++)
       {
           if(!vis[j]&&dis[j]<mindis)
           {
               mindis=dis[j];
               mark=j;
           }
       }
       vis[mark]=1;
       for(j=0;j<n;j++)
       {
           if(!vis[j])
           {
               dis[j]=min(dis[j],dis[mark]+w[mark][j]);
           }
       }
    }
    if(dis[y]==inf)
    {
       printf("-1\n");
       return ; 
    }
        
    else
    {
        printf("%d\n",dis[y]);
        return ;
     } 
        
}
void init()
{
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            w[i][j]=inf;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,a,b,c;
        init();
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(c<w[a][b]) w[a][b]=w[b][a]=c;
        }
        scanf("%d%d",&x,&y);
        dijstra();
    }
    return 0;
}

这样只能拿到一半的分,数据点应该只有2个,因为输出一个“-1”就能拿到50分
2019-12-01 14:11
Jason_
Rank: 2
来 自:浙江台州
等 级:论坛游民
帖 子:43
专家分:66
注 册:2019-7-14
  得分:0 
回复 4楼 Jason_
不好意思这题代码贴错了,这应该是另一题的代码
2019-12-02 18:52
快速回复:请各位帮我看看这道题,谢谢!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.062120 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved