任意图的最大匹配.cpp

任意图的最大匹配算法

/*
*任意图的最大匹配
*照搬毕升的算法库
*熟悉一下这种算法
*现在还不太清楚算法核心
*/

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
#define MaxV 55
#define INF 100000000
int visit[MaxV][2];
int map[MaxV][MaxV];
int mat[MaxV],n,m;

void in()
{
	memset(map,0,sizeof(map));
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int s,t;
		scanf("%d%d",&s,&t);
		map[s][t] = map[t][s] = 1;
	}
}

void Find_Way(int s,int t)
{
	int i,j;
	i = s;
	j = t;
	mat[t] = s;
	while(visit[i][1] < INF)
	{
		mat[i] = j;
		j = visit[i][1];
		mat[j] = visit[j][0];
		i = visit[j][0];
	}
	mat[i] = j; 
}

bool kuo_tree()
{
	int i,k,j,q,v;
	set<int> s;
	bool more;
	do{
		more = false;
		for(i=1;i<=n;i++)
		{
			if(visit[i][1] > 0)
			{
				for(j=1;j<=n;j++)
					if(map[i][j]>0 && mat[i]!=j)
					{
						if(visit[j][0] == 0 && visit[j][1] == 0)
						{
							if(mat[j] == 0)
							{
								Find_Way(i,j);
								return true;
							}
							else
							{
								map[i][j] = -map[i][j];		map[j][i] = - map[j][i];
								visit[j][0] = i;		visit[mat[j]][1] = j;
								map[j][mat[j]] = -map[j][mat[j]];
								map[mat[j]][j] = -map[mat[j]][j];
								more = true;
							}
						}
						else if(visit[j][0]==0 && visit[j][1] > 0)
						{
							more = true;
							map[i][j] = -map[i][j];		map[j][i] = -map[j][i];
							s.clear();			s.insert(i);
							k = i;				v = 1;
							while(visit[k][v] < INF)
							{
								k = visit[k][v];
								s.insert(k);
								v = 1 - v;
							}
							k = j;		v = 1;
							while(s.find(k) == s.end())
							{
								k = visit[k][v];
								v = 1 - v;
							}
							if(visit[i][0] == 0)
							{
								visit[i][0] = j;
								q = i;		v = 1;
								while(q != k)
								{
									visit[visit[q][v]][v] = q;
									q = visit[q][v];
									v = 1 - v;
								}
							}
							visit[j][0] = i;
							q = j;		v = 1;
							while(q != k)
							{
								visit[visit[q][v]][v] = q;
								q = visit[q][v] ;
								v = 1 - v;
							}
								
						}
					}
			}
		}
	}while(more);
	return false;
}


int Match()
{
	int i,j,k,ans = 0;
	bool find;
	memset(mat,0,sizeof(mat));//the tag numbered from 1,so initance the array by 0
	do{
		i=0;
		do{
			i++;
			if(mat[i] == 0)
			{
				memset(visit,0,sizeof(visit));
				visit[i][1] = INF;
				find = kuo_tree();
				for(j=1;j<=n;j++)
					for(k=1;k<=n;k++)
						if(map[j][k] < 0)
							map[j][k] = -map[j][k];
			}
			else
				find = false;
		}while(i<=n && !find);
		if(i <= n)	ans++;
	}while((i<=n) && (ans != n/2));
	return ans;
}

int main()
{
	//freopen("1.txt","r",stdin);
	int T,i;
	scanf("%d",&T);
	while(T--)
	{
		in();
		if(Match()*2 == n)
			printf("bob\n");
		else
			printf("alice\n");
	}
	return 0;
}