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 ;}
代码修修改改好多次才过的,所以很挫....