二进制方程630row.cpp

设计一个算法

 #include<iostream.h>
#include<stdio.h>
#include <fstream>
using namespace std;
template <class T> class List;
void OutOfBounds(){};
int COUNT;
//----------------------------------------------------------------------------------------
class UnionFind
{
public:
	UnionFind(int n);
	~UnionFind()
	{
		delete []parent;
		delete []root;
	}
	int Find(int e);
	void Union(int i,int j);
private:
	int *parent;
	bool *root;
};
//---------------------------------------------------------------------------------------
UnionFind::UnionFind(int n)
{
	root=new bool[n+1];
	parent=new int[n+1];
	for(int e=1;e<=n;e++)
	{
		parent[e]=1;
		root[e]=true;
	}
}
//---------------------------------------------------------------------------------------
int UnionFind::Find(int e)
{
	int j=e;
	while(!root[j])
		j=parent[j];
	int f=e;
	while(f!=j)
	{
		int pf=parent[f];
		parent[f]=j;
		f=pf;
	}
	return j;
}
//----------------------------------------------------------------------------------------
void UnionFind::Union(int i,int j)
{
	if(parent[i]<parent[j])
	{
		parent[j]+=parent[i];
		root [i]=false;
		parent[i]=j;
	}
	else
	{
		parent[i]+=parent[j];
		root[j]=false;
		parent[j]=i;
	}
}
//------------------------------------------------------------------------------------------
template<class T>
class Node
{
	friend class List<T>;
private:
	T data;
	Node<T> *next;
};
//------------------------------------------------------------------------------------------
template<class T>
class List
{
private:
	Node<T> *first;
public:
	List(){first=0;}
	~List();
	List<T>& Insert(int k,const T& x);
	void OutList(T *s,int n);
};
//------------------------------------------------------------------------------------------
template<class T>
List<T>::~List()
{
	Node<T> * next;
	while(first)
	{
		next=first->next;
		delete first;
		first=next;
	}
}
//------------------------------------------------------------------------------------------
template<class T>
List<T>& List<T>::Insert(int k,const T& x)
{
	if(k<0) throw OutOfBounds();
	Node<T> *p=first;
	for(int index=1;index<k&&p;index++)
		p=p->next;
	if(k>0&&!p) throw OutOfBounds();
	Node<T> *y=new Node<T>;
	y->data=x;
	if(k)
	{
		y->next=p->next;
		p->next=y;
	}
	else
	{
		y->next=first;
		first=y;
	}
	return * this;
}
//-------------------------------------------------------------------------------------------
template<class T>
void List<T>::OutList(T *S,int n)
{
	Node<T> * current;
	for( current=first;current;current=current->next)
	{
		S[n]=current->data;
	    n++;
	}
	COUNT=n;
}
//===========================================================================================
void main()
{
    ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	ofstream out("output.txt");
    int LeftEqation[100000];
	int RightEqation[100000];
	int NumEqation;
    in>>NumEqation;
	int ExchangeNum;
	int Num,Number;
	for(int i=0;i<NumEqation;i++)
	{
		in>>ExchangeNum;
		Number=2;
		List<int> *store=new List<int> [ExchangeNum+2];
		store[0].Insert(0,0);
		store[1].Insert(0,1);
		int L;
		int Sum=0;
		//-----------------------------------
		for(int j=0;j<ExchangeNum;j++)
		{
			in>>Num;
			Sum=Sum+Num;
			L=0;
			for(int k=0;k<Num;k++)
			{
				store[j+2].Insert(L,Number);
				Number++;
				L++;
			}
		}
		//-----------------------------------        store the Number into comfortble structure; 
		int Strenthleft;
	    int Strenthright;
	    int *p=LeftEqation;
		int *q=RightEqation;
		int countleft=0;
		int countright=0;
		in>>Strenthleft;
		char *Left=new char[Strenthleft];
		for(int n=0;n<Strenthleft;n++)
		{
			in>>Left[n];
			if(Left[n]=='1'||Left[n]=='0')
			{
				LeftEqation[countleft]=Left[n]-48;
			    countleft++;
			}
			else
			{
				int u;
				char y;
				y=Left[n];
				u=y-95;
                store[u].OutList(p,countleft);
				countleft=COUNT;				
			}
		}
		in>>Strenthright;	
		char *Right=new char[Strenthright];
		for(int r=0;r<Strenthright;r++)
		{
			in>>Right[r];
	        if(Right[r]=='1'||Right[r]=='0')
			{
				RightEqation[countright]=Right[r]-48;
     			countright++;
			}
			else
			{
				int v;
				char z;
				z=Right[r];
				v=z-95;
				store[v].OutList(q,countright);
				countright=COUNT;
			}
		}
		if(countleft!=countright)
		{
			out<<"-1"<<endl;
			continue;
		}
		else
		{
			int A,B;
			int c=-1,e=0;
			int Count=Sum+2;
			UnionFind Storage(Sum+2);
			for(int x=0;x<countright;x++)
			{
				A=Storage.Find(LeftEqation[x]);
				B=Storage.Find(RightEqation[x]);
				if(A!=0&&A!=1)
				{
					if(B==0||B==1)
					{
						if(c!=B&&e<=2)
						{e++;}
						Storage.Union(B,A);
						LeftEqation[x]=B;
						Count--;
						c=B;
					}
					else if(B!=0&&B!=1)
					{
						if(A!=B)
						{
							Storage.Union(A,B);
							Count--;
						}
					}
				}
				else if(A==1||A==0)
				{
					if(c!=A&&e<=2)
					{e++;}
					if(B==(1-A))
					{
						out<<"-1"<<endl;
						goto Loop;
					}
					else
					{
						if(B!=0&&B!=1)
						{
							Storage.Union(A,B);
							RightEqation[x]=A;
							Count--;
							c=A;
						 }
					}
				}
			}
			out<<Count-(2-e)-e<<endl;
			delete []store;
			delete []Left;
			delete []Right;
		}
Loop:continue;
	}
}
//======================================================================================