程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3896 dfs樹倍增

HDU 3896 dfs樹倍增

編輯：C++入門知識

Greatest TC

Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 509 Accepted Submission(s): 148

Problem Description TC (Tian Chao) is magical place, as you all know...
The railways and the rail-stations in TC are fragile and always meet with different kinds of problems. In order to reach the destination safely on time, you are asked to develop a system which has two types of main functions as below.
1: A B C D, reporting whether we can get from station A to station B without passing the railway that connects station C and station D.
2: A B C, reporting whether we can get from station A to station B without passing station C.
Please notice that the railways are UNDIRECTED.
Input For each test case, the first line will contain two integers N (2<=N<=100000) and M (1<=M<=500000), namely the number of stations and railways in TC. Then each of the next M lines will have two integers, describing the two stations that a certain railway is connecting. After this, there comes a line containing a single integer Q (Q<=300000), which means the number of queries to make on the system. The next Q lines will be queries. Each query begins with a integer, indicating the type of query, followed by 4 (the first type) or 3 (the second type) integers describing the details of the query as what mentioned above.
The stations are always labeled from 1 to N.
Output For each test case, print "yes" or "no" in separated lines for the queries.
Sample Input

Sample Output

yes
yes
yes
no
yes

題意:給定一個圖，有兩種詢問，第一種，從a-b是否經過c-d的路徑，從a-b是否經過c點。
根據tarjan可以得到一個dfs序，記錄第一次經過這個點的時間戳，已經離開這個點的時間戳，每一個點只訪問一次，
記錄預處理倍增數組。
對於查詢1，假設c在d的下邊，討論a,b與c的關系，假如a，b都是c的子樹上的點，或者都不是，那麼顯然存在，只需要討論
一個在c的子樹上，一個不在的情況，假如a在c的子樹上假如a的low值小於等於c的dfn，則顯然可以，否則不能。
對於查詢2，假如a，b都不在c的子樹上，則顯然可以。
假如都在c的子樹上，那麼找a，b在c下方的點pp，qq，假如pp==qq，則顯然不需要經過c，如果pp，qq都可以查找到c前面的點，那麼a，b可以經過pp，qq
到達c的前面，顯然可以繞過c相遇。
剩下的就是a，b中有一個在c的子樹上，假如a，那麼找a在c下方的那個點pp，假如pp存在，那麼看pp是否可以返祖到c的前面，假如可以，那麼肯定可以
找到不經過c的路徑。
好惡心的題目，折騰了一天，在別人的指導下終於ac了，wa30次，坑爹。
代碼：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/2 13:43:24
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=101000;
const int maxm=1001000;
int head[maxn],tol;
int low[maxn],dfn[maxn],indexx;
int fa[maxn][20],dep[maxn],out[maxn];
int vis[maxm];
struct Edge{
    int next,to;
}edge[maxm];
void addedge(int u,int v){
    edge[tol].to=v;
    edge[tol].next=head[u];
    head[u]=tol++;
}
void tarjan(int u,int deep){
    low[u]=dfn[u]=++indexx;
    dep[u]=deep;
    for(int i=head[u];i!=-1;i=edge[i].next){
        if(vis[i])continue;
        vis[i]=vis[i^1]=1;
        int v=edge[i].to;
        if(!dfn[v]){
            tarjan(v,deep+1);
            fa[v][0]=u;
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],dfn[v]);
    }
    out[u]=indexx;
}
bool judge1(int a,int b,int c,int d){
    if(dep[c]=dfn[c]&&out[a]<=out[c])ina=1;
    if(dfn[b]>=dfn[c]&&out[b]<=out[c])inb=1;
    if((ina&&inb)||(!ina&&!inb))return 1;
    else{
        if(low[c]<=dfn[d])return 1;
        return 0;
    }
}
int move(int x,int step){
    if(step<0)return -1;
    for(int i=19;i>=0;i--)
        if((1<=dfn[c]&&out[a]<=out[c])ina=1;
    if(dfn[b]>=dfn[c]&&out[b]<=out[c])inb=1;
    int flag=0;
    if(!ina&&!inb)flag=1;
    else if(ina&&!inb){
        int pp=move(a,dep[a]-dep[c]-1);
        if(pp!=-1&&low[pp]