posts - 176, comments - 60, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

1789

Posted on 2007-02-12 02:47 魔のkyo 阅读(56) 评论(0)  编辑 收藏 引用

 

// 2007-02-12 02:13:52    Accepted    1789    C++    00:00.04    2988K
// 一次AC
// 算法:分支限界法(用队列搜)

#include 
< iostream >
#include 
< vector >
#include 
< queue >
#include 
< numeric >
using   namespace  std;

typedef vector
< int >  vector_int;

int  main ()
{
    
int  n,m;
    
while (scanf( " %d %d " , & n, & m) != EOF  &&  (n || m)){
        
int  marked_person[ 30000 ] = { 1 },marked_group[ 500 ] = { 0 }; // 标记有嫌疑的人,和有嫌疑的组
        queue < int >  Q; // 用来BFS有嫌疑的组
        vector_int *  vGroup = new  vector_int [m];
        vector_int
*  vPerson = new  vector_int [n];
        
for ( int  i = 0 ;i < m;i ++ ){
            
int  k,t;
            scanf(
" %d " , & k);
            
for ( int  j = 0 ;j < k;j ++ ){
                scanf(
" %d " , & t);
                vGroup[i].push_back(t);
// Group i中有t这个成员
                vPerson[t].push_back(i); // Person t参加了i这个组
                 if ( ! t){
                    marked_group[i];
// 标记所有包含0这个成员的Group
                    Q.push(i); // 有嫌疑的组入队
                }
            }
        }

        
while ( ! Q.empty()){
            
int  tempQNode = Q.front(); // 取出一个嫌疑组
            Q.pop();
            
for ( int  i = 0 ;i < vGroup[tempQNode].size();i ++ ){ // 遍历嫌疑组中的所有人
                 int  tempPerson = vGroup[tempQNode][i];
                
if ( ! marked_person[tempPerson]){ // 如果这个人没有被标记过
                    marked_person[tempPerson] = 1 ; // 标记嫌疑人
                     for ( int  j = 0 ;j < vPerson[tempPerson].size();j ++ ){ // 遍历这个人所加入的所有组
                         int  tempGroup = vPerson[tempPerson][j];
                        
if ( ! marked_group[tempGroup]){ // 如果嫌疑人加入的组没有被标记过
                            marked_group[tempGroup] = 1 ; // 标记嫌疑组
                            Q.push(tempGroup); // 嫌疑组入队
                        }
                    }
                }
            }
        }
        printf(
" %d\n " ,accumulate(marked_person,marked_person + n, 0 ));
        delete [] vGroup;
        delete [] vPerson;
    }
}
只有注册用户登录后才能发表评论。