1293.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1293 on 2006-03-07 at 12:48:22 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 256;

class Pair {
public:
	int a, b;
	void set(int, int);
};
void Pair::set(int ca, int cb) {
	a = ca; b = cb;
}

int main()
{
	int t, T, i, j;
	Pair per[2*MAX];
	bool dan[MAX][MAX], chg[MAX][MAX], vst[2][MAX];
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		memset(dan, false, sizeof(dan));
		int n, m; scanf("%d %d", &n, &m);
		int lmt = n / 2;
		for(i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b);
			dan[a-1][b-1] = true;
		}
		memset(vst, false, sizeof(vst)); int pn = 0;
		for(i = 0; i < n; i++) {
			if(vst[0][i]) continue;
			int an[2] = { 0, 0 }; queue<int> Q;
			Q.push(i<<1); an[0]++; vst[0][i] = true;
			while(!Q.empty()) {
				int p = Q.front(), s = p&1, o = p>>1; Q.pop();
				for(j = 0; j < n; j++) {
					if(vst[1-s][j] || (s == 0 && !dan[o][j]) || (s == 1 && !dan[j][o])) continue;
					vst[1-s][j] = true; an[1-s]++; Q.push((j<<1)|(1-s));
				}
			}
			per[pn++].set(an[0], an[1]);
		}
		for(i = 0; i < n; i++)
			if(!vst[1][i]) per[pn++].set(0, 1);
		memset(chg, false, sizeof(chg));
		int state[MAX*MAX], sn = 0;
		state[sn++] = 0;
		for(i = 0; i < pn; i++) {
			int x = sn;
			for(j = 0; j < x; j++) {
				int sa = state[j]>>8, sb = state[j]&255;
				sa += per[i].a; sb += per[i].b;
				if(sa > lmt || sb > lmt || chg[sa][sb]) continue;
				chg[sa][sb] = true; state[sn++] = (sa << 8) | sb;
			}
		}
		for(i = lmt; i > 0; i--)
			if(chg[i][i]) break;
		printf("%d\n", i);
	}
	
	
	return 0;
}