The Castle
        IOI'94
       
        题目大意:
                http://www.nocow.cn/index.php/Translate:USACO/castle
               
        分析:
            题面和要求有点啰嗦,不过总的来说还是好理解的。给定一个城堡的规格,让你求
        在围墙内可以互相联通的小房间组成的大房间的个数和尺寸。另外设法推倒一面墙,让
        两个大房间合并成更大的房间。
            这题嘛,我也不知道该分析什么,当时一看到就用图论观点做了。下面给出几个入
        手点(其实和NOCOW的大同小异了):
       
        1.并查集
            显然一堆互相联通的小房间属于同一个等价集 ,对二位的数据扫一遍然后映射到一
        维的并查集上求并。最后森林的个数自然就是大房间的个数了,一颗树的重量就是房间的
        尺寸了。这个出来推墙就好办,枚举每一面合法的墙,两边的房间求一次树根,如果不同
        根(重要细节,如果墙两次的房间是同一个大房间的话就错了~)则按要求做比较。最后
        打印,收工。
       
         2.floodfill
            刚开始我也不清楚这个做法(之前确实不知道,汗~)。后来看了下usaco的论文。
        其实还是很形象的,就是用BFS往上灌水,任何联通的区域都会被当前这次灌的水淹到。
        不同次灌水淹到的区域自然就是不同的大房间了。仍然不清楚的请看usaco上的论文。
       
         3.硬搞
            实在不会的何必想那么多呢,让小房间构成n*m的无向图,没有门的房间自然
        相邻。直接DFS联通分支。打印,收工。
       
        下面给出我的并查代码的 main(),求出门的方位使用位运算

 

int main(){
        
for(step=0;step<2600;step++) ufs[step]=-1;
        fscanf(fin,
"%d%d",&n,&m);
        
for(step=0;step<m;step++)
                
for(step2=0;step2<n;step2++)
                        fscanf(fin,
"%d",&room[step][step2]);
               
        
for(step=0;step<m;step++)
                
for(step2=0;step2<n;step2++){
                        tmpNum
=room[step][step2];
                        digit
=0;
                        pos1
=step*n+step2;
                        
while(1){
                                
if( (tmpNum&1==0){
                                        pos2
=(step+door[digit][0])*n+(step2+door[digit][1]);
                                        ufsF(ufs,pos1,pos2);   
// 并查相邻两个房间
                                }

                                tmpNum
>>=1;
                                digit
++;
                                
if(tmpNum==0&&digit>3break;
                        }

                }

        roomNum
=0;
        maxSize
=0;
        
for(step=0;step<m*n;step++){
                
if(ufs[step]<0){
                        
if(ufs[step]*-1>maxSize) maxSize=ufs[step]*-1;
                        roomNum
++;
                }

        }

        fprintf(fout,
"%d\n%d\n",roomNum,maxSize);
       
        maxAdd
=0;
        
for(step2=0;step2<n;step2++)
            
for(step=m-1;step>-1;step--){   
                tmpNum
=room[step][step2];
                digit
=0;
                pos1
=(step)*n+step2;
                
while(1){
                     
if((tmpNum&1)==1){
                        
if(digit==2||digit==1){
                           
// 从左下到右上检查每个小房间与右、上有墙隔着的小房间,若不同根则计算

                           
if(step+door[digit][0]>-1&&step2+door[digit][1]<n){  // 门不是墙壁
                               pos2=(step+door[digit][0])*n+(step2+door[digit][1]);
                               root1
=Find(ufs,pos1);
                               root2
=Find(ufs,pos2);
                               
if(root1!=root2){
                                  
if(maxAdd< (ufs[root1]+ufs[root2])*-1 ){
                                     maxAdd
=(ufs[root1]+ufs[root2])*-1;
                                     rm
=step+1; rn=step2+1;
                                     rd
=(digit==1)?'N':'E';
                                  }

                               }

                           }

                       }

                     }

                     tmpNum
>>=1;
                     digit
++;
                     
if(tmpNum==0&&digit>3break;
                }
       
           }

        fprintf(fout,
"%d\n%d %d %c\n",maxAdd,rm,rn,rd);
        
return 0;
}


 

Your satisfaction is necessary to our success. Our goal is to provide you with the best level of customer service, and we welcome your comments and suggestions

Email:

Sales: sales@CuteSoft.Net  

General: info@CuteSoft.Net

Support: support@CuteSoft.Net

Address:


CuteSoft
35 SHERWOOD CRES
BELLEVILLE, ON
K8P 5G2
Canada