Median Weight Bead Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 3162 Accepted: 1630 Description

For example, the following results show which bead is heavier after M comparisons where M=4 and N=5. 1. Bead 2 is heavier than Bead 1.

From the above results, though we cannot determine exactly which is the median bead, we know that Bead 1 and Bead 4 can never have the median weight: Beads 2, 4, 5 are heavier than Bead 1, and Beads 1, 2, 3 are lighter than Bead 4. Therefore, we can remove these two beads.

Write a program to count the number of beads which cannot have the median weight. Input

The first line of the input file contains a single integer t (1 <= t <= 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows: The first line of input data contains an integer N (1 <= N <= 99) denoting the number of beads, and M denoting the number of pairs of beads compared. In each of the next M lines, two numbers are given where the first bead is heavier than the second bead. Output

There should be one line per test case. Print the number of beads which can never have the medium weight. Sample Input

1 5 4 2 1 4 3 5 1 4 2 Sample Output

2

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
int a[105][105];
int b[105][105];
int n,m;
void floyed1()
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&a[i][k]&&a[k][j])
a[i][j]=1;
}
}
}
}
void floyed2()
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&b[i][k]&&b[k][j])
b[i][j]=1;
}
}
}
}
int main()
{
int t;
int x,y;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x][y]=1;
b[y][x]=1;
}
floyed1();
floyed2();
int res=0;
for(int i=1;i<=n;i++)
{
int num1=0;
for(int j=1;j<=n;j++)
{
if(a[i][j])
num1++;
}
int num2=0;
for(int j=1;j<=n;j++)
{
if(b[i][j])
num2++;
}
if(num1>(n/2)||num2>(n/2))
res++;
}
printf("%d\n",res);

}
}

497 篇文章45 人订阅

0 条评论

## 相关文章

### HDUOJ------1058 Humble Numbers

Humble Numbers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

35580

### ZOJ 3332 Strange Country II

Strange Country II ---- Time Limit: 1 Second      Memory Limit: 32768 KB      Sp...

36150

### hdu----(3118)Arbiter(构造二分图)

Arbiter Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K ...

33850

### HDUOJ-----Computer Transformation

Computer Transformation Time Limit: 2000/1000 MS (Java/Others)    Memory Limi...

389110

27460

### HDUOJ1086You can Solve a Geometry Problem too

You can Solve a Geometry Problem too Time Limit: 2000/1000 MS (Java/Others)    M...

27460

### HDUOJ------2398Savings Account

Savings Account Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

31870

### HDUoj-------（1128）Self Numbers

Self Numbers Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/327...

35850

### POJ 3461 kmp

Oulipo Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 40168 ...

30460

### hdu----（2586）How far away ？（DFS/LCA/RMQ）

How far away ？ Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

28980