算法

POJ1975总结

Median Weight Bead

题目来源

Description

There are N beads which of the same shape and size, but with different weights. N is an odd number and the beads are labeled as 1, 2, …, N. Your task is to find the bead whose weight is median (the ((N+1)/2)th among all beads). The following comparison has been performed on some pairs of beads:
A scale is given to compare the weights of beads. We can determine which one is heavier than the other between two beads. As the result, we now know that some beads are heavier than others. We are going to remove some beads which cannot have the medium weight.

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.

2. Bead 4 is heavier than Bead 3.
3. Bead 5 is heavier than Bead 1.
4. Bead 4 is heavier than Bead 2.

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

我的代码

将大小关系按照有向图的方式存储到二维数组map[][]中(有边为1,无边为0),如果一个钢珠比另一个重,意味着这个钢珠到另一个钢珠有一条有向边。如果两个钢珠有路径可以到达的话,就直接在这两个钢珠之间画一个有向边。问题转化为求出度大于(N+1)/2或入度大于(N+1)/2的钢珠的个数。

处理方式是如果一个钢珠i,存在钢珠j使得i的重量大于j的重量(map[i][j]!=0),那么在图的数组中第i行对应加上第j行。最终只要两个点在数组中不等于0,就说明它们存在大小关系(有路径)。

优化:在求路径时需要不断向下搜索直到根节点,可以使用记忆化搜索来减少复杂度;对于一些出度为0的点可以不用去搜索其能达到的范围。设flag数组,当flag[i]=0时表示出度为0,不需要搜索,当flag[i]=1时出度不为0,且此时仍未进行搜索,当flag[i]=2时表示出度不为0,但是已经搜索过了,可以直接进行运算。

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

int t,n,m,a,b;
int map[100][100];
int flag[100];

void dfs(int now)
{
	flag[now]=2;
	for (int i=1;i<=n;i++)
	{
		if (map[now][i]==1)
		{
			if (flag[i]==2)
			{
				for (int j=1;j<=n;j++)
				{
					map[now][j]+=map[i][j];
				}
			}
			else if (flag[i]==1)
			{
				dfs(i);
				for (int j=1;j<=n;j++)
				{
					map[now][j]+=map[i][j];
				}
			}
		}
	}
}

int main()
{

	scanf("%d",&t);
	while(t--)
	{
		int ans=0,num;
		scanf("%d%d",&n,&m);
		num=(n+1)/2;
		memset(map,0,sizeof(map));
		memset(flag,0,sizeof(flag));
		while (m--)
		{
			scanf("%d%d",&a,&b);
			map[a][b]=1;
			flag[a]=1;
		}
		for (int i=1;i<=n;i++)
		{
			if (flag[i]==1) dfs(i);
		}
		for (int i=1;i<=n;i++)
		{
			int temp=0;
			for (int j=1;j<=n;j++)
			{
				if (map[i][j]!=0) temp++;
			}
			if (temp>=num) ans++;
		}
		for (int i=1;i<=n;i++)
		{
			int temp=0;
			for (int j=1;j<=n;j++)
			{
				if (map[j][i]!=0) temp++;
			}
			if (temp>=num) ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

发表评论