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

【题目链接】

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 + 二分)

• 编辑
• 预览