HDU 3715 Go Deeper(2-SAT + 二分)

shuangde800 · · 1345 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

【题目链接】

http://acm.hdu.edu.cn/showproblem.php?pid=3715


【题目大意】

有一个递归代码:


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;
}



有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:shuangde800

查看原文:HDU 3715 Go Deeper(2-SAT + 二分)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1345 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传