信息学奥赛一本通T1384：图的连通性问题 珍珠

【题目描述】有n颗形状和大小都一致的珍珠，它们的重量都不相同。n为整数，所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间，即在所有珍珠的重量中，该珍珠的重量列(n+1)/2位。下面给出将一对珍珠进行比较的办法：给你一架天平用来比较珍珠的重量，我们可以比出两个珍珠哪个更重一些，在作出一系列的比较后，我们可以将某些肯定不具备中间重量的珍珠拿走。例如，下列给出对5颗珍珠进行四次比较的情

信息学奥赛一本通T1384：珍珠

【题目描述】

有n颗形状和大小都一致的珍珠，它们的重量都不相同。n为整数，所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间，即在所有珍珠的重量中，该珍珠的重量列(n+1)/2位。下面给出将一对珍珠进行比较的办法：

给你一架天平用来比较珍珠的重量，我们可以比出两个珍珠哪个更重一些，在作出一系列的比较后，我们可以将某些肯定不具备中间重量的珍珠拿走。

例如，下列给出对5颗珍珠进行四次比较的情况：

1、珍珠2比珍珠1重

2、珍珠4比珍珠3重

3、珍珠5比珍珠1重

4、珍珠4比珍珠2重

根据以上结果，虽然我们不能精确地找出哪个珍珠具有中间重量，但我们可以肯定珍珠1和珍珠4不可能具有中间重量，因为珍珠2、4、5比珍珠1重，而珍珠1、2、3比珍珠4轻，所以我们可以移走这两颗珍珠。

写一个程序统计出共有多少颗珍珠肯定不会是中间重量。

【输入】

第一行包含两个用空格隔开的整数N和M，其中1≤N≤99，且N为奇数，M表示对珍珠进行的比较次数，接下来的M行每行包含两个用空格隔开的整数x和y，表示珍珠x比珍珠y重。

【输出】

一行包含一个整数，表示不可能是中间重量的珍珠的总数。

【输入样例】

5 4
2 1
4 3
5 1
4 2

【输出样例】

2

【源程序】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 501
#define MOD 123
#define E 1e-6
using namespace std;
int g[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=1;
    }

    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            for(int j=1;j<=n;j++)
                if(g[k][i]&&g[i][j])
                    g[k][j]=1;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            g[0][j]+=g[i][j];
            g[i][0]+=g[i][j];
        }

    int cnt=0;
    for(int i=1;i<=n;i++)
        if( g[0][i]>n/2 || g[i][0]>n/2 )
            cnt++;

    cout<<cnt<<endl;
    return 0;
}

 

信息学奥赛一本通T1384：图的连通性问题 珍珠 归属于 图的连通性问题，更多同类题解源程序见：图的连通性问题 和 珍珠

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！