aa.cpp

罗马支配数的算法

#include <iostream.h>




#define Max_V_Num 1000



main()
{
	int i,j,l,v[Max_V_Num],sm[Max_V_Num],k1,k2,k3,
		state[Max_V_Num][4],adjv[Max_V_Num][4],
		result[Max_V_Num],modnum,n,mod,k,segrn,p,q;
	double re[Max_V_Num],romn,totalromn,check;



	cout<<"请输入广义Petersen图P(n,2)的n值(n>=5)：";
	cin>>n;


	


     		mod=7;
			segrn=8;
			modnum=n/mod;
			if(n%mod==0)
				romn=modnum*segrn;
			else if(n%mod==1) 
				romn=modnum*segrn+2;
			else if(n%mod==2) 
				romn=modnum*segrn+3;
			else if(n%mod==3) 
				romn=modnum*segrn+4;
			else if(n%mod==4) 
				romn=modnum*segrn+5;
			else if(n%mod==5) 
				romn=modnum*segrn+6;
			else if(n%mod==6) 
				romn=modnum*segrn+7;
			romn+=1;

	


		for(i=1;i<=2*n;i++)
		{
			if(i%2==1)
			{
				adjv[i][0]=i;
				j=i-2;
				if(j<=0)j+=2*n;
				adjv[i][1]=j;
				adjv[i][2]=i+1;
				j=i+2;
				if(j>2*n)j-=2*n;
				adjv[i][3]=j;
			}//if(i%2==1)
			else
			{
				adjv[i][0]=i;
				j=i-4;
				if(j<=0)j+=2*n;
				adjv[i][1]=j;
				adjv[i][2]=i-1;
				j=i+4;
				if(j>2*n)j-=2*n;
				adjv[i][3]=j;
			}//if(i%2==1)else		
		}//for(i=1;i<=2*n;i++)

		
		
		q=-1;
		sm[0]=0;
		for(i=1;i<=2*n;i++)
		{
			sm[i]=0;
			re[i]=1;
			
		}

		v[0]=1;
	
		for(j=0;j<4;j++)
		{
			p=adjv[1][j];
			state[1][j]=sm[p];
			
			if(sm[p])
			{
				re[p]+=0.5;
			}
			else
			{
				re[p]-=0.5;
				sm[p]=1;
			}
		
		}//for(j=0;j<4;j++)
	
		l=1;
		j=v[l-1];
		j++;  
		totalromn=0;
		for(i=1;i<=2*n;i++)
		{
			totalromn=totalromn+re[i];
		}//for(i=1;i<=2*n;i++)
		if(totalromn<romn)
		{
			romn=totalromn;
			q=l-1;
			for(i=0;i<=q;i++)
			{
				result[i]=v[i];
			}

		}//if(totalromn<romn)


		do{
			if(j<=2*n)
			{
				if(j%2==1)
				{
					
					k1=j;
					k2=j-2;
					if(k2<=0)
						k2+=2*n;
					k3=j+1;
					

				}//if(j%2==1)
				else
				{
				
					k1=j-4;
					if(k1<=0) 
						k1+=2*n;
					k2=j;
					k3=j-1;
					if(k3<=0) 
						k3+=2*n;
					

				}//if(j%2==1)else
				
						
				if( (sm[k1]+sm[k2]+sm[k3])<2 )
				{

					for(i=0;i<4;i++)
					{
						p=adjv[j][i];
						state[j][i]=sm[p];
					
						if(sm[p])
						{
							re[p]+=0.5;
						}
						else
						{
							re[p]-=0.5;
							sm[p]=1;
						}
					
					}//for(j=0;j<4;j++)
				
					
					v[l]=j;
				
					++l;
				
					totalromn=0;
					check=0;
					for(i=1;i<=2*n;i++)
					{
						totalromn+=re[i];
						if(sm[i])
							check+=re[i];
						else
							check+=0.5;
					}//for(i=1;i<=2*n;i++)
				
				
					if(totalromn<romn)
					{
						romn=totalromn;  
						q=l-1;
						for(i=0;i<=q  ;i++)
						{
							result[i]=v[i];
						
						}
					
					}//if(totalrn<rn)
					if(check>=romn)
					{
						j=v[--l];
						for(i=0;i<4;i++)
						{
							p=adjv[j][i];
							sm[p]=state[j][i];
							
							if(sm[p])
							{
								re[p]-=0.5;
							}
							else
							{
								re[p]+=0.5;
							}
							
						}//for(j=0;j<4;j++)
						
					

					}//if(check>=rn)

				}//if( (sm[k1]+sm[k2]+sm[k3])<2 )
				j++;
			}//if(j<=2*n)
			else
			{
			
				j=v[--l];

				for(i=0;i<4;i++)
				{
					p=adjv[j][i];
					sm[p]=state[j][i];
					
					if(sm[p])
					{
						re[p]-=0.5;
					}
					else
					{
						re[p]+=0.5;
					}
				
				}//for(j=0;j<4;j++)
				
				j++;
			}//if(j<=2*n) else
		}while(l>0);//do_while()

	

	
	cout<<"广义Petersen图P("<<n<<",2)的罗马支配数为："<<romn<<endl;
	cout<<"广义Petersen图P("<<n<<",2)的结点为2的结点号为："<<endl;

	for(i=0;i<=q;i++)
	{
		
		cout<<result[i]<<"\t";
	}//for(i=0;i<=q;i++)
	cout<<endl;

	
}//main()