mymaxmatch.cpp

也是一个关于匹配方面的程序

			}
			cout<<"赋值后链表匈牙利树显示完毕"<<endl;
			cout<<"下面显示T的元素："<<endl;
			for(tmpi = 0; tmpi < g.n; tmpi++)
			{
				register int tmpj = 0;
				for(tmpj = 0; tmpj < g.n; tmpj++)
				{
					cout<<T[tmpi][tmpj]<<',';
				}
				cout<<endl;
			}
			cout<<"T元素显示完毕"<<endl;
			tmp = Ts.back().treeMatch;
			cout<<"下面显示treematch的元素："<<endl;
			for(tmpi = 0; tmpi < g.n; tmpi++)
			{
				register int tmpj = 0;
				for(tmpj = 0; tmpj < g.n; tmpj++)
				{
					cout<<tmp[tmpi][tmpj]<<',';
					//cout<<Ts.back().treeMatch[tmpi][tmpj];
				}
				cout<<endl;
			}
			cout<<"treematch元素显示完毕"<<endl;*/
#endif
			if(T[i][j] != -1)
			{
				Ts.back().treeMatch[i][j] = (matchEdge[i][j] && T[i][j]) || (matchEdge[i][j] && T[j][i]);
				Ts.back().treeMatch[j][i] = Ts.back().treeMatch[i][j];
			}
		}
	}
	//在图中去掉匈牙利树的点和关联的边，等
#if DEBUGMYMAXMATCH == 1
	Ts.back().printTree();
	Ts.back().printTreeMatch();
#endif
	int tnum = tv.size();
	for(i = 0; i < tnum; i++)
	{
		g.Vertex[tv[i]].num = -1;
		register int j = 0;
		for(j = 0; j < g.n; j++)
		{
			g.Edge[tv[i]][j].isE = 0;
			g.Edge[j][tv[i]].isE = 0;
			matchEdge[tv[i]][j] = 0;
			matchEdge[j][tv[i]] = 0;
			//hutMatchE[][]??匈牙利树本身也有匹配边??
		}
	}
#if DEBUGMYMAXMATCH == 1
	cout<<endl;
	cout<<"去掉匈牙利树后，";
	printG();
#endif
	//去掉所有节点的标号
	for(i = 0; i < g.n; i++)
	{
		label[i] = 0;
	}
	//生长下一棵交替树
	T = NULL;
	T = new int*[g.n];
	for(i = 0; i < g.n; i++)
	{
		T[i] = new int[g.n];
	}
	for(i = 0; i < g.n; i++)
	{
		register int j = 0;
		for(j = 0; j < g.n; j++)
		{
			T[i][j] = 0;//0表示没有边
			testEdge[i][j] = 0;//应该吧???
		}
	}
#if DEBUGMYMAXMATCH == 1
	cout<<"...匈牙利树处理完毕..."<<endl;
#endif
	//tv.clear();//清除原来的T节点
}
void MyMaxMatch::printM()
{
	int i = 0;
	cout<<"匹配边集合为："<<'{';
	for(i = 0; i < g.n; i++)
	{
		register int j = 0;
		for(j = i; j < g.n; j++)
		{
			if(matchEdge[i][j] > 0)
			{
				cout<<'('<<i<<','<<j<<')'<<' ';
			}
		}
	}
	cout<<'}'<<endl;	
}
void MyMaxMatch::printG()
{
	cout<<"打印图的状态..."<<endl;
	cout<<"图的邻接矩阵为："<<endl;
	int i = 0;
	int j = 0;
	for(i = 0; i < g.n; i++)
	{
		cout<<g.Vertex[i].num<<':';
		for(j = 0; j < g.n; j++)
		{
			cout<<g.Edge[i][j].isE<<',';
		}
		cout<<endl;
	}
	cout<<endl;
	cout<<"图的边为:"<<endl;
	for(i = 0; i < g.n; i++)
	{
		for(j = 0; j < g.n; j++)
		{
			if(g.Edge[i][j].isE == 1)
			{
				cout<<'('<<i<<','<<j<<')'<<"  ";
			}
		}
		cout<<endl;
	}
}
void MyMaxMatch::printT()
{
	cout<<"交错树的边为:"<<endl;
	int i = 0;
	int j = 0;
	for(i = 0; i < g.n; i++)
	{
		for(j = 0; j < g.n; j++)
		{
			if(T[i][j] > 0)
			{
				cout<<'('<<i<<','<<j<<')'<<"  ";
			}
		}
		cout<<endl;
	}
}

//myBlossom
MyMaxMatch::MyBlossom::MyBlossom()
{
	vIndex = -1;
	treeIndex = -1;
	Edge = NULL;
	//Edge = new int*
}
MyMaxMatch::MyBlossom::MyBlossom(const MyBlossom& b)
{
	n = b.n;
	vertex = b.vertex;
	vIndex = b.vIndex;
	treeIndex = b.treeIndex;
/*	if(Edge != NULL)
	{
		for(register int i = 0; i < n; i++)
		{
			delete[] Edge[i];
		}
		delete[] Edge;
	}*///为什么这里会出错？而graph里面就没有错？
	Edge = NULL;
	if(b.Edge !=NULL)
	{
		int i = 0;
		int j = 0;
		Edge = new int*[n];
		for(i = 0; i < n; i++)
		{
			Edge[i] = new int[n];
		}
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				Edge[i][j] = b.Edge[i][j];
			}
		}
	}	
}
void MyMaxMatch::MyBlossom::initialE()
{
	if(Edge != NULL)
	{
		for(register int i = 0; i < n; i++)
		{
			delete[] Edge[i];
		}
		delete[] Edge;
	}
	Edge = NULL;
	Edge = new int*[n];
	int i = 0;
	for(i = 0; i < n; i++)
	{
		Edge[i] = new int [n];
	}
	for(i = 0; i < n; i++)
	{
		register int j = 0;
		for(j = 0; j < n; j++)
		{
			Edge[i][j] = 0;
		}
	}
}
void MyMaxMatch::MyBlossom::printBlossom()
{
	cout<<"the blossom vetex from the base is :"<<endl;
	int i = 0;
	for(i = 0; i < vertex.size(); i++)
	{
		cout<<vertex[i]<<',';
	}
	cout<<"->"<<vertex[0]<<endl;
}
void MyMaxMatch::MyBlossom::printEdge()
{
	if(Edge != NULL)
	{
		cout<<"the blossom edge is :"<<endl;
		int i = 0;
		int j = 0;
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				if(Edge[i][j] == 1)
				{
					cout<<'('<<i<<','<<j<<')'<<"  ";
				}
			}
			cout<<endl;
		}		
	}	
}
MyMaxMatch::MyBlossom& MyMaxMatch::MyBlossom::operator=(const MyBlossom& b)
{
	n = b.n;
	vertex = b.vertex;
	vIndex = b.vIndex;
	treeIndex = b.treeIndex;
	if(Edge != NULL)
	{
		for(register int i = 0; i < n; i++)
		{
			delete[] Edge[i];
		}
		delete[] Edge;
	}
	int i = 0;
	int j = 0;
	Edge = new int*[n];
	for(i = 0; i < n; i++)
	{
		Edge[i] = new int[n];
	}
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			Edge[i][j] = b.Edge[i][j];
		}
	}
	return *this;
}/**/
MyMaxMatch::MyBlossom::~MyBlossom()
{
	if(Edge != NULL)
	{
		for(register int i = 0; i < n; i++)
		{
			delete[] Edge[i];
		}
		delete[] Edge;
	}
}

//myHut

MyMaxMatch::MyHut::MyHut()
{
	treeMatch = NULL;
	tree = NULL;
	num = 0;
	treeMatch = new int*[num];
	int i = 0;
	for(i = 0; i < num; i++)
	{
		treeMatch[i] = new int[num];
	}
	for(i = 0; i < num; i++)
	{
		register int j = 0;
		for(j = 0; j < num; j++)
		{
			treeMatch[i][j] = 0;
		}
	}	
}
MyMaxMatch::MyHut::MyHut(int num)
{
	tree = NULL;
	treeMatch = NULL;
	this->num = num;
	treeMatch = new int*[num];
	int i = 0;
	for(i = 0; i < num; i++)
	{
		treeMatch[i] = new int[num];
	}
	for(i = 0; i < num; i++)
	{
		register int j = 0;
		for(j = 0; j < num; j++)
		{
			treeMatch[i][j] = 0;
		}
	}
}
MyMaxMatch::MyHut::MyHut(const MyHut& h)
{
	num = h.num;
	tv = h.tv;
	tree = NULL;
	treeMatch = NULL;
	if(h.tree != NULL)
	{
		tree = new int*[num];
		int i = 0;
		int j = 0;
		for(i = 0; i < num; i++)
		{
			tree[i] = new int[num];
		}
		for(i = 0; i < num; i++)
		{
			for(j = 0; j < num; j++)
			{
				tree[i][j] = h.tree[i][j];				
			}
		}
	}
	if(h.treeMatch != NULL)
	{
		treeMatch = new int*[num];
		int i = 0;
		int j = 0;
		for(i = 0; i < num; i++)
		{
			treeMatch[i] = new int[num];
		}
		for(i = 0; i < num; i++)
		{
			for(j = 0; j < num; j++)
			{
				treeMatch[i][j] = h.treeMatch[i][j];
			}
		}
	}
}
MyMaxMatch::MyHut& MyMaxMatch::MyHut::operator=(const MyHut& h)
{
	num = h.num;
	tv = h.tv;
	int i = 0;
	int j = 0;
	if(tree != NULL)
	{
		for(i = 0; i < num; i++)
		{
			delete[]tree[i];
		}
		delete []tree;
	}
	if(treeMatch != NULL)
	{
		for(i = 0; i < num; i++)
		{
			delete[]treeMatch[i];
		}
		delete []treeMatch;
	}
	tree = NULL;
	treeMatch = NULL;
	tree = new int*[num];
	treeMatch = new int*[num];
	for(i = 0; i < num; i++)
	{
		tree[i] = new int[num];
		treeMatch[i] = new int[num];
	}
	for(i = 0; i < num; i++)
	{
		for(j = 0; j < num; j++)
		{
			tree[i][j] = h.tree[i][j];
			treeMatch[i][j] = h.treeMatch[i][j];
		}
	}
	return *this;
}
MyMaxMatch::MyHut::~MyHut()
{
	//释放treeMatch的空间
	int i = 0; 
	if(treeMatch != NULL)
	{
		for(i = 0; i < num; i++)
		{
			delete[]treeMatch[i];
		}
		delete []treeMatch;
	}
	if(tree != NULL)
	{
		for(i = 0; i < num; i++)
		{
			delete[]tree[i];
		}
		delete []tree;
	}
}
void MyMaxMatch::MyHut::printTreeMatch()
{
	int i = 0;
	cout<<"匈牙利树匹配边集合为："<<'{';
	for(i = 0; i < num; i++)
	{
		register int j = 0;
		for(j = i; j < num; j++)
		{
			if(treeMatch[i][j] > 0)
			{
				cout<<'('<<i<<','<<j<<')'<<' ';
			}
		}
	}
	cout<<'}'<<endl;	
}
void MyMaxMatch::MyHut::printTree()
{
	cout<<"匈牙利树的边为:"<<endl;
	int i = 0;
	int j = 0;
	for(i = 0; i < num; i++)
	{
		for(j = 0; j < num; j++)
		{
			if(tree[i][j] > 0)
			{
				cout<<'('<<i<<','<<j<<')'<<"  ";
			}
		}
		cout<<endl;
	}
}