poj2942 解题报告

本来想下午做完了周末好好玩,结果尼玛做了一晚上...

题意:

亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：

1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置；

2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。

如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。

现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个骑士才能顺利召开会议

( 我找网上的题意,自己说不清楚 )

题解:

1,将图求反,就是把有的边去掉,将没有的添上

2,找到双连通块

3,在双连通块中找是否存在奇圈,若存在则块中的骑士都可以开会的

4,统计有多少骑士不能存在在大于1的奇圈中的

代码:

#include <iostream>#include <cstring>#include <cstdio>#include <stack>#include <queue>using namespace std ;const int MAXN = 1005 ;const int MAXM = MAXN * MAXN * 2 ;struct type{    int  end , next ;} ;type  edge[MAXM] ;int   head[MAXN] , Count , mark[MAXN]    ;int   low[MAXN]  , dfn[MAXN] , vis[MAXN] ;int   map[MAXN][MAXN] , num[MAXN] , belone[MAXN]  ;int   color[MAXN] ;stack < int > Stack ;void  addedge( int start , int end ){    edge[Count].end  = end         ;    edge[Count].next = head[start] ;    head[start]      = Count ++    ;}int  bfs( int cur , int from ){    memset( color , -1 , sizeof( color ) ) ;    queue < int > q ;    q.push( cur ) ;    color[cur] = 0 ;    while( !q.empty() )    {        int  temp = q.front() ;        q.pop() ;        for( int i = head[temp] ; i != -1 ; i = edge[i].next )        {            int end = edge[i].end ;            if( belone[end] != from ) continue ;            if( color[end] == 1 - color[temp] ) continue ;            if( color[end] == -1 )            {                color[end] = 1 - color[temp] ;                q.push( end ) ;            }            else if( color[end] == color[temp] ) return 1 ;        }    }    return 0 ;}void  tarjan_dfs( int cur , int father , int & cnt , int & Time ){    Stack.push( cur ) ;    dfn[cur] = low[cur] = Time ++ ;    vis[cur] = 1 ;    for( int i = head[cur] ; i != -1 ; i = edge[i].next )    {        int  end = edge[i].end ;        if( end == father ) continue ;        if( !vis[end] )        {            tarjan_dfs( end , cur , cnt , Time )  ;            low[cur] = min( low[cur] , low[end] ) ;            if( dfn[cur] <= low[end] )            {                int  temp , Cnt = 0 ;                cnt ++ ;                do                {                    temp = Stack.top() ;                    Stack.pop() ;                    num[Cnt] = temp ;                    belone[temp] = cnt ;                    Cnt ++ ;                }while( temp != end ) ;                num[Cnt] = cur ;                belone[cur] = cnt ;                Cnt ++ ;                if( bfs( cur , cnt ) ){                    for( int j = 0 ; j < Cnt ; j ++ ){                        mark[num[j]] = 1 ;                    }                }            }        }        else low[cur] = min( low[cur] , dfn[end] ) ;    }}int   tarjan( int n ){    int  Time = 0 , cnt = 0 ;    memset( dfn , 0 , sizeof( dfn ) ) ;    memset( low , 0 , sizeof( low ) ) ;    memset( vis , 0 , sizeof( vis ) ) ;    memset( num , 0 , sizeof( num ) ) ;    memset( belone , -1 , sizeof( belone ) ) ;    for( int i = 1 ; i <= n ; i ++ ){        if( !vis[i] ) tarjan_dfs( i , -1 , cnt , Time ) ;    }    return cnt ;}int  main(){    int  m , n , i , j ;    int  start , end ;    while( scanf( "%d%d" , & n , & m ) && n && m )    {        memset( head , -1 , sizeof( head ) ) ;        memset( map  ,  0 , sizeof(  map ) ) ;        memset( mark ,  0 , sizeof( mark ) ) ;        Count = 0 ;        while( m -- )        {            scanf( "%d%d" , & start , & end ) ;            map[start][end] = 1 ;            map[end][start] = 1 ;        }        for( i = 1 ; i <= n ; i ++ )            for( j = 1 ; j <= n ; j ++ )            {                if( i == j ) continue ;                if( !map[i][j] ) addedge( i , j ) ;            }        int  ans  = 0 ;        int  temp = tarjan( n ) ;        for( i = 1 ; i <= n ; i ++ )            if( mark[i] == 0 ) ans ++ ;        printf( "%d\n" , ans ) ;    }    return 0 ;}

代码修修改改好多次才过的,所以很挫....