1766.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
int edge[32][32],sign[32];
int e[][2]={{0,1},{0,2},{0,3},{0,4},{0,5},
	    {11,6},{11,7},{11,8},{11,9},{11,10},
	    {1,2},{2,3},{3,4},{4,5},{5,1},
	    {6,7},{7,8},{8,9},{9,10},{10,6},
	    {1,6},{1,7},
	    {2,7},{2,8},
	    {3,8},{3,9},
	    {4,9},{4,10},
	    {5,10},{5,6},
	    };
void find(int a)
{int i;
for(i=0;i<32;i++)
	if(edge[a][i]&&sign[i]==0){sign[i]=1;find(i);}
}


int main()
{int i,j,a,b,k,h,n,yes,no,past;
for(i=0;i<32;i++)
for(j=0;j<32;j++)edge[i][j]=0;

for(i=0;i<30;i++)
{a=e[i][0];b=e[i][1];edge[a][b]=edge[b][a]=1;}

h=12;
for(i=0;i<12;i++)
for(j=i+1;j<12;j++)
for(k=j+1;k<12;k++)
if(edge[i][j]&&edge[i][k]&&edge[j][k])
	{edge[h][i]=edge[i][h]=1;
	 edge[h][j]=edge[j][h]=1;
         edge[h][k]=edge[k][h]=1;	 
	h++;
	}

for(i=0;i<12;i++)
for(j=i+1;j<12;j++)
if(edge[i][j])
	{for(k=12;k<32;k++)
	 for(h=k+1;h<32;h++)
	 if(edge[i][k]&&edge[i][h]&&edge[j][k]&&edge[j][h])
	 {edge[k][h]=edge[h][k]=1;}
	}

for(i=0;i<32;i++)sign[i]=0;

for(i=0;i<12;i++)
for(j=0;j<12;j++)edge[i][j]=0;
/*
for(i=0;i<32;i++)
{for(j=0;j<32;j++)
cout<<edge[i][j]<<' ';cout<<endl;}
*/

sign[12]=1;sign[13]=-1;
yes=12;no=13;past=-1;
cin>>n;

while(n--)
{cin>>a;
for(h=0;h<32;h++)if(edge[yes][h]&&edge[no][h]&&h!=past)break;
//cout<<h<<endl;		
if(a==1){sign[h]=-1;past=no;no=h;}
else {sign[h]=1;past=yes;yes=h;}
}

for(i=0;i<32;i++)
if(sign[i]==1)find(i);

int gs=0,bs=0,ws=0;
for(i=0;i<32;i++){
	if(sign[i]==1)gs++;
	else {if(i<12)bs++;
		else ws++;
		}
	}
cout<<bs<<' '<<ws<<' '<<gs<<endl;
return 0;
}