算法：HDU 3715 Go Deeper（2-SAT + 二分）

【题目大意】

有一个递归代码：

go(int dep, int n, int m)

begin

    output the value of dep.

if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)

end

关键是看第四行， 如果满足条件dep < m and x[a [dep]] + x[b[dep]] != c[dep] 那么就可以进入下一层递归， x数组只取{0, 1}， c数组取{ 0，1，2 }, 而a和b数组取0～m， m是最大能递归的层数，也是数组x的大小。  问最多能递归多少层？

【思 路】

对于每个x【i】， 只能取0或者1， 在每一层中如果满足条件就可以进入下一层，这个题非常像  poj 2723 ， 做法也是一样的。

二分最多能递归的层数，然后对这些层数进行2-sat的建图， 判断即可。

【代码】

#include<iostream>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<vector>
#define MP make_pair
#define SQ(x) ((x)*(x))
using namespace std;  

const int INF  = 0x3f3f3f3f;
const int MAXN = 10010;
const int VN = MAXN*2;
const int EN = VN*4;  

int n, m, s;
int a[MAXN], b[MAXN], c[MAXN];  

struct Graph{
    int size, head[VN];
    struct{int v, next; }E[EN];
    void init(){size=0; memset(head, -1, sizeof(head)); };
    void addEdge(int u, int v){
        E[size].v = v;
        E[size].next = head[u];
        head[u] = size++;
    }
}g;  

class Two_Sat{
public:
    bool check(const Graph& g, const int n){
        scc(g, 2*n);
        for(int i=0; i<n; ++i)
            if(belong[i] == belong[i+n])
                return false;
        return true;
    }
private:
    void tarjan(const Graph& g, const int u){
        int v;
        dfn[u] = low[u] = ++idx;
        sta[top++] = u;
        instack[u] = true;  

        for(int e=g.head[u]; e!=-1; e=g.E[e].next){
            v = g.E[e].v;
            if(dfn[v] == -1){
                tarjan(g, v);
                low[u] = min(low[u], low[v]);
            }else if(instack[v]){
                low[u] = min(low[u], dfn[v]);
            }
        }  

        if(dfn[u] == low[u]){
            ++bcnt;
            do{
                v = sta[--top];
                instack[v] = false;
                belong[v] = bcnt;
            }while(u != v);
        }
    }  

    void scc(const Graph& g, const int n){
        idx = top = bcnt = 0;
        memset(dfn, -1, sizeof(dfn));
        memset(instack, 0, sizeof(instack));
        for(int i=0; i<n; ++i){
            if(dfn[i] == -1)
                tarjan(g, i);
        }
    }  

private:
    int idx, top, bcnt;
    int dfn[VN], low[VN], sta[VN], belong[VN];
    bool instack[VN];
}sat;  

void buildGraph(int dep){
    g.init();
    for(int i=0; i<dep; ++i){
        int x=a[i], y=b[i];
        if(c[i]==0){
            g.addEdge(x, y+m);
            g.addEdge(y, x+m);
        }else if(c[i] == 1){
            g.addEdge(x, y);
            g.addEdge(x+m, y+m);
            g.addEdge(y, x);
            g.addEdge(y+m, x+m);
        }else if(c[i] == 2){
            g.addEdge(x+m, y);
            g.addEdge(y+m, x);
        }
    }  

}
int main(){  

    int nCase;
    scanf("%d", &nCase);  

    while(nCase--){  

        scanf("%d%d", &n, &m);  

        for(int i=0; i<m; ++i){
            scanf("%d%d%d", &a[i], &b[i], &c[i]);
        }  

        int l=0, r=m+1, mid, ans;
        while(l < r){
            mid = (l + r) >> 1;
            buildGraph(mid);
            if(sat.check(g, m)){
                l = mid+1;
                ans = mid;
            } else r = mid;
        }
        printf("%d\n", ans);
    }  

    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， 递归
， int
， include
， const
， head
递归二分查找算法
we need to go deeper、we need go deeper、go deeper、gosation、长沙分时租赁 sat go，以便于您获取更多的相关知识。