#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define MM 250
int m,r;

struct posision 
{
	int x,y;
	posision(){}
	posision(int x,int y)
	{
		this->x=x;
		this->y=y;
	}
	bool operator == (posision &other)
	{
		return x==other.x&&y==other.y;
	}
	bool operator != (posision &other)
	{
		return x!=other.x&&y!=other.y;
	}
};



struct rank
{
	int amount;
	int left;
	int right;
};

posision father[MM][2];
rank rk[MM][2];
vector<rank> group;
bool dp[MM][MM];
vector<posision> feasible;
vector<posision> future;
void iniUnionSet();
bool isRoot(posision p);
posision find(posision p);
bool merge(posision x,posision y);
void readData();
void grouping();
void dpSolve();
void solve();
void ini();
int main()
{
	int css;
	scanf("%d",&css);
	while(css--)
	{
		scanf("%d%d",&m,&r);
		ini();
		readData();
		grouping();
		dpSolve();
		solve();
	}
	return 0;
}


void iniUnionSet()
{
	int i;
	for(i=1;i<=m;i++)
	{
		father[i][0]=posision(i,0);
		father[i][1]=posision(i,1);
		rk[i][0].left = 1;
		rk[i][0].right = 0;
		rk[i][0].amount = 1;
		rk[i][1].left = 0;
		rk[i][1].right = 1;
		rk[i][1].amount = 1;
	}
	group.clear();
}

bool isRoot(posision p)
{
	return find(p)==p;
}

posision find(posision p)
{
	if(father[p.x][p.y]!=p)
		father[p.x][p.y] = find(father[p.x][p.y]);
	return father[p.x][p.y];
}

bool merge(posision x,posision y)
{
	//printf("merge{%d,%d} , {%d,%d}\n",x.x,x.y,y.x,y.y);
	posision fx,fy;
	fx = find(x);
	fy = find(y);
	if(fx == fy)
	{
		return false;
	}
	else
	{
		if(rk[fx.x][fx.y].amount>=rk[fy.x][fy.y].amount)
		{
			rk[fx.x][fx.y].amount += rk[fy.x][fy.y].amount;
			rk[fx.x][fx.y].left += rk[fy.x][fy.y].left;
			rk[fx.x][fx.y].right += rk[fy.x][fy.y].right;
			father[fy.x][fy.y] = x;
			rk[fy.x][fy.y].amount = 0;
			//printf("to fx\n");
		}
		else
		{
			rk[fy.x][fy.y].amount += rk[fx.x][fx.y].amount;
			rk[fy.x][fy.y].left += rk[fx.x][fx.y].left;
			rk[fy.x][fy.y].right += rk[fx.x][fx.y].right;
			father[fx.x][fx.y] = y;
			//printf("to fy\n");
		}
		//posision p = find(x);
		//printf("father={%d,%d}\n",p.x,p.y);
		return true;
	}
	return true;
}

void readData()
{
	int i;
	int xi,yi;
	for(i=0;i<r;i++)
	{
		scanf("%d%d",&xi,&yi);
		merge(posision(xi,0),posision(yi,1));
	}
}


void grouping()
{
	int i;
	for(i=1;i<=m;i++)
	{
		if(isRoot(posision(i,0)))
			group.push_back(rk[i][0]);
		if(isRoot(posision(i,1)))
			group.push_back(rk[i][1]);
	}
	//printf("size=%d\n",group.size());
}




void dpSolve()
{
	int i,j;
	int nx,ny;

	dp[0][0] = true;
	int m2 = m/2;
	feasible.push_back(posision(0,0));
	for(i=0;i<group.size();i++)
	{
		for(j=0;j<feasible.size();j++)
		{
			nx = feasible[j].x+group[i].left;
			ny = feasible[j].y+group[i].right;
			if(nx<=m2&&ny<=m2&&(!dp[nx][ny]))
			{
				dp[nx][ny] = true;
				future.push_back(posision(nx,ny));
			}
		}
		for(j=0;j<future.size();j++)
		{
			feasible.push_back(future[j]);
		}
		future.clear();
	}
}

void solve()
{
	int i;
	for(i=m/2;i>=0;i--)
	{
		if(dp[i][i])
		{
			printf("%d\n",i);
			return;
		}
	}
}
void ini()
{
	iniUnionSet();
	memset(dp,false,sizeof(dp));
	feasible.clear();
	future.clear();
}

• Re:重写了一遍,wa了…… (2278) hataksumo 2013-02-17 16:44:18