030300326_2.cpp

这是一个关于字典问题的源程序

#include<iostream>
#include<fstream>
using namespace std;
ifstream in ("input.txt");
ofstream out ("output.txt");
//并查集类
class UnionFind
{
public:
	UnionFind(int n);
	~UnionFind(){delete[] parent;delete[] root;}
	int Find(int e);
	void Union(int i,int j);
	int * parent;
	bool * root;
};
UnionFind::UnionFind(int n)
{
	root=new bool[n+1];
	parent=new int[n+1];
	for(int e=0;e<=n;e++)
	{
		parent[e]=1;
	    root[e]=true;
	}
}
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;
	}
}
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 main()//主函数
{
 int num,u;
 in>>num;//输入方程数
 for(u=0;u<num;u++)
 {
	int n,x,y,i,j,k,g,h;
	int	m=0,len1=0,len2=0,jienum;
	char w;
	in>>n;
	int * q=new int [n+1];
	int * t=new int [n+1];
	t[0]=2;
	for(i=0;i<n;i++)
	{
	  in>>q[i];
	  m=m+q[i];
	  t[i+1]=t[i]+q[i];
	}
    int b[90000],c[90000];
    UnionFind p(m+2);jienum=m;
	in>>x;//处理左端方程，把每位二进制用数值表示 
	  for(i=0;i<x;i++)
	  {
       in>>w;
	    if(w=='1')
		{
		   b[len1]=1;
		   len1++;
		}
		else if(w=='0')
		{
		   b[len1]=0;
		   len1++;
		}
	    else 
		{
			k=t[w-97];
			for(j=0;j<q[w-97];j++)
			{
				b[len1]=k;
				len1++; k++;
			}
		}
	  }
	 in>>y;//处理右端方程，把每位二进制用数值表示
	  for(i=0;i<y;i++)
	  {
       in>>w;
	    if(w=='1')
		{
		   c[len2]=1;
		   len2++;
		}
		else if(w=='0')
		{
		   c[len2]=0;
		   len2++;
		}
	    else 
		{
			k=t[w-97];
			for(j=0;j<q[w-97];j++)
			{
				c[len2]=k;
				len2++; k++;
			}
		}
	  }
	if(len1==len2)
	{ //处理等价条件
	  for(i=0;i<len1;i++)
		  if(b[i]==c[i]);
		  else if(b[i]==0 && c[i]==1 || b[i]==1 && c[i]==0)
			  goto end;//如有1=0或0=1则直接为无解跳出
          else
		  {
			  g=p.Find(b[i]);h=p.Find(c[i]);
			  if(g!=h)
			  { p.Union(g,h); jienum--;}
		  } 
	  out<<jienum<<endl;
	}
	else
end:  out<<-1<<endl;
	delete []q;
	delete []t;
 }
}