gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

Pku 3678--Katu Puzzle

2-SAT 問題
關鍵：建圖（建議先看趙爽的論文）

#include <stdio.h>

#include <cstring>

#include <stack>

using namespace std ;

const int MAXN = 2005 ;

struct Node{

int ID;

Node *next;

}mapa[MAXN] ;

Node gTemp[110001] ;

int gPos = 0 ;

int N , M ; //點數邊數

int g_Pred[MAXN], g_Num[MAXN], SN, flag[MAXN] ;

bool visited[MAXN];

stack<int> g_Stack ;

void Insert(int a, int b)

{

Node *p = &gTemp[gPos++];

p->ID = b;

p->next = mapa[a].next;

mapa[a].next = p;

}

void Build( const int& a , const int& b, const int& c, const char* cmd )

{

if ( strcmp( cmd , "AND" ) == 0 )

{

if ( c == 1 )

{

Insert( a + N, a ) ;

Insert( b + N, b ) ;

}

else {

Insert( a, b + N ) ;

Insert( b, a + N ) ;

}

else if ( strcmp( cmd , "OR" ) == 0 )

{

if ( c == 1 )

{

Insert( a + N , b ) ;

Insert( b + N , a ) ;

}

else {

Insert( a, a + N ) ;

Insert( b, b + N ) ;

}

else if ( strcmp( cmd , "XOR" ) == 0 )

{

if ( c == 1 )

{

Insert( a + N , b ) ;

Insert( b + N , a ) ;

Insert( b , a + N ) ;

Insert( a , b + N ) ;

}

else {

Insert( a + N , b + N ) ;

Insert( b + N , a + N ) ;

Insert( a , b ) ;

Insert( b , a ) ;

}

int MIN( const int& a, const int& b )

{

return ( a < b ? a : b ) ;

}

// Tarjan算法求SCC

void StrongDFS( int v )

{

g_Pred[v] = g_Num[v] = SN++ ;

g_Stack.push( v ) ;

Node *ptr = mapa[v].next ;

visited[v] = true ;

while ( ptr ){

if ( g_Num[ptr->ID] == 0 )

{

StrongDFS( ptr->ID ) ;

g_Pred[v] = MIN( g_Pred[v], g_Pred[ptr->ID] ) ;

}

else if ( g_Num[ptr->ID] < g_Num[v] && !visited[ptr->ID] )

{

g_Pred[v] = MIN( g_Pred[v], g_Num[ptr->ID] ) ;

}

ptr = ptr->next ;

}

if ( g_Pred[v] == g_Num[v] )

{

int w = g_Stack.top() ;

g_Stack.pop() ;

while ( w != v )

{

flag[w] = SN ;

w = g_Stack.top() ;

g_Stack.pop() ;

}

flag[w] = SN ;

}

void StronglyCon()

{

int i ;

memset(g_Num, 0, sizeof(g_Num)) ;

memset(visited, 0, sizeof(visited)) ;

memset(flag, 0, sizeof(flag)) ;

SN = 1 ;

for ( i = 0 ; i < N * 2 ; ++i )

{

if ( g_Num[i] == 0 )

StrongDFS( i ) ;

}

void Init()

{

gPos = 0 ;

int i ;

for ( i = 0 ; i < MAXN ; ++i )

{

mapa[i].next = NULL ;

}

while ( !g_Stack.empty() )

{

g_Stack.pop() ;

}

int main()

{

int i , first , second , third ;

char cmd[8] ;

while ( scanf("%d %d", &N, &M) != EOF )

{

Init() ;

for ( i = 0 ; i < M ; ++i )

{

scanf("%d %d %d %s", &first, &second, &third, &cmd) ;

Build( first, second, third, cmd ) ;

}

StronglyCon() ;

bool ans = true ;

for ( i = 0 ; i < N ; ++i )

{

if ( flag[i] == flag[i + N] )

{

ans = false ;

break ;

}

if ( ans )

{

printf("YES\n") ;

}

else {

printf("NO\n") ;

}

return 0 ;

}

posted on 2008-10-30 23:26 巫閱讀(383) 評論(0) 編輯收藏引用所屬分類: 圖論

只有注冊用戶登錄后才能發表評論。


相關文章: POJ 3662--Telephone Lines(二分枚舉 + Dij) POJ 3268(最短路徑 SPFA) POJ 1511(SPFA) POJ 1511(Dij + Heap) POJ 1094(簡單的拓撲排序) Pku 2226--Muddy Fields Pku 3678--Katu Puzzle

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論