题意分析

题目描述了一组珠子，其中每个珠子的重量不同，且珠子的数量N为奇数。我们需要找出这些珠子中重量处于中位数位置的珠子。通过给定的M次比较结果（每次比较指出哪个珠子更重），我们可以排除那些不可能是中位数的珠子。 中位数位置：由于N是奇数，中位数位置为第 $\frac{N+1}{2}$重的珠子。 比较结果：每次比较结果给出两个珠子的重量关系。 排除条件： 如果一个珠子比超过$\frac{N-1}{2}$个其他珠子轻，则它不可能是中位数。 如果一个珠子比超过$\frac{N-1}{2}$个其他珠子重，则它不可能是中位数。

解题思路

1.输入处理：读取测试用例的数量T，然后逐个处理每个测试用例。

2.初始化：对于每个测试用例，初始化一个N×N的二维数组a，用于记录珠子之间的重量关系。

3.记录比较结果：将每次比较结果存入数组a，其中a[u][v] = 1表示珠子u比珠子v重。

4.传递闭包：使用Floyd-Warshall算法计算所有珠子之间的重量关系，即如果u比v重，v比w重，那么u也比w重。

5.统计入度和出度： 对于每个珠子i，统计比它重的珠子数量（入度in[i]）。统计比它轻的珠子数量（出度out[i]）。 排除非中位数珠子：如果一个珠子的入度或出度超过 $\frac{N-1}{2}$，则该珠子不可能是中位数。

代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=100+5;
bool a[MAXN][MAXN];

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int m,n;
		scanf("%d%d",&n,&m);
		int cmp=(n+1)/2;
		for(int i=1;i<=n;i++)               //初始化
			for(int j=1;j<=n;j++) a[i][j]=0;//用memset也可以
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			a[u][v]=1;                      //emm..u比v重
		}
		for(int k=1;k<=n;k++)               //Floyed传递闭包
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					a[i][j]=(a[i][j]||(a[i][k]&&a[k][j]));
		int ans=0,in[MAXN],out[MAXN];
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				if(a[i][j]&&i!=j)
					out[i]++,in[j]++;
			}
		for(int i=1;i<=n;i++)
			if(in[i]>=cmp||out[i]>=cmp) ans++;
		printf("%d\n",ans);                 
	}
	return 0;
}