row.cpp

设计一个有效算法

#include<iostream>
#include<fstream>
using namespace std;
#include"time.h"


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;
	}
}



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;
}


clock_t start,finish;
int main()
{start=clock();
	ifstream in("input.txt");
    if(in.fail())
    {cout<<"the input.txt is not exist!\n";
     exit(1);
	}
    ofstream out("output.txt");

	int n,m,leftlength,rightlength,num=2,l=0,lr=0,sum=0;
	int length[27];
	in>>n;
	for(int s=1;s<=n;s++)
	{
		in>>m;
		for(int i=1;i<=m;i++)
			in>>length[i];
		in>>leftlength;
		char *sl=new char [leftlength+1];
		for(i=1;i<=leftlength;i++)
			in>>sl[i];
		in>>rightlength;
		char *sr=new char [rightlength+1];
		for(i=1;i<=rightlength;i++)
			in>>sr[i];
		for(i=1;i<=leftlength;i++)
		{
			if(sl[i]=='0'||sl[i]=='1') l++;
			else
			{
				int temp1=sl[i]-96;
				l+=length[temp1];
			}
		}
		for(i=1;i<=rightlength;i++)
		{
			if(sr[i]=='0'||sr[i]=='1') lr++;
			else
			{
				int temp=sr[i]-96;
				lr+=length[temp];
			}
		}
		if(l!=lr) 
		{
			out<<"-1"<<endl;
			delete [] sl;
		    delete [] sr;
			num=2;l=0;lr=0;
            continue;
		}
		int *left=new int [l];
		int *right=new int [l];
		i=1;
		for(int j=1;j<=leftlength;j++)
		{
			if(sl[j]=='0'||sl[j]=='1')
			{
				left[i]=int(sl[j])-47;     //注意
				i++;
			}
			else
			{
				int temp2=sl[j]-96;
				for(int t=1;t<temp2;t++) sum+=length[t];
				for(t=1;t<=length[temp2];t++)
				{
					left[i]=sum+2+t;
					i++;
				}
				sum=0;
			}
		}
		i=1;
		sum=0;
		for(j=1;j<=rightlength;j++)
		{
			if(sr[j]=='0'||sr[j]=='1')
			{
				right[i]=int(sr[j])-47;    //注意
				i++;
			}
			else
			{
				int temp3=sr[j]-96;
				for(int t=1;t<temp3;t++) sum+=length[t];
				for(t=1;t<=length[temp3];t++)
				{
					right[i]=sum+2+t;
					i++;
				}
				sum=0;
			}
		}
		for(i=1;i<=m;i++)
			num+=length[i];
		UnionFind U(num);
		int count=num;
		for(i=1;i<=l;i++)
		{
			int root1=U.Find(left[i]);
			int root2=U.Find(right[i]);
			if(root1==root2) continue; //注意
			U.Union(root1,root2);
			count--;
		}
		if(U.Find(1)==U.Find(2))
			out<<"-1"<<endl;
		else
		    out<<count-2<<endl;
    	delete [] sl;
		delete [] sr;
		//delete [] left;          //为什么？？
		//delete [] right;
		num=2;l=0;lr=0;sum=0;       //注意
	}
	finish=clock();
    cout<<finish-start<<endl;
	return 0;
}