1289.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1289 on 2006-11-10 at 21:41:05 */
#include <cstdio>
#include <algorithm>
using namespace std;
 
typedef long long int64;
const int N = 40;
const int64 ALL = (1LL << 40)-1;
 
int opt;
int64 p[N];
 
int dnum(int64);
void dfs(int, int, int64);
 
int main()
{
	int T;
 
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		memset(p, 0, sizeof(p));
		int n; scanf("%d", &n);
		for(int i = 0; i < n; i++) {
			int a, b; scanf("%d %d", &a, &b);
			p[a] |= 1LL << b;
		}
		opt = 0;
		dfs(0, 0, ALL);
		printf("%d\n", opt);
	}
 
	return 0;
}
 
void dfs(int d, int lk, int64 st)
{
	if(d == N) return;
	else if(p[d] == 0) dfs(d+1, lk, st);
	else {
		int64 nst = st&p[d];
		int nd = dnum(nst);
		opt >?= min(nd, lk+1);
		if(nd > lk+1) dfs(d+1, lk+1, nst);
		dfs(d+1, lk, st);
	}
}
int dnum(int64 k)
{
	int dn = 0;
	for(int i = 0; i < N; i++)
		if(k&(1LL<<i)) dn++;
	return dn;
}