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最多能达到什么值?由题意可知dep<=m,其中a与b与c数组都是m大小的,数组下标从0到m,然后x数组是下标从0到n-1的.且c数组的取值为0或1或2.a与b数组的取值是0到n-1.x数组的取值是0或1.
现在给出了a,b,c数组对应下标的所有值,但是还不知道x数组的取值,问你如果你来设定x的值,可以使dep最大达到多少?
分析:
由于x数组只能去0或1,可以看出该题就是2-SAT问题. 我们只要2分dep的值即可的出解.
假设当前dep=mid,然后对于下标从0到mid-1来说,有下面关系:
x[a[0]]+x[b[0]] != c[0]
x[a[1]]+x[b[1]] != c[1]
…
x[a[mid-1]]+x[b[mid-1]] !=c[mid-1]
然后我们合理的设置一下x数组的值,看看是否能满足这前mid个条件.由于a,b,c数组的值都已经知道了,比如a[0]=1,b[0]=2,c[0]=2
有x[1]+x[2] !=2 ,那么我们可以推出边: add_clause(1,1,2,0)且 add_clause(2,1,1,0).
一般性结论有:
x[a]+x[b]= 0 -> add(a,0,b,1) add(b,0,a,1)
x[a]+x[b]=1 ->add(a,1,b,1) add(a,0,b,0) add(b,1,a,1)add(b,0,a,0)
x[a]+x[b]=2 ->add(a,1,b,0) add(b,1,a,0)
二分dep,建图2-SAT,直接解决.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn= 200 +10;
const int maxm= 10000+10;
int n,m;
int a[maxm],b[maxm],c[maxm];
struct TwoSAT
{
int n;
vector<int> G[maxn*2];
int S[maxn*2],c;
bool mark[maxn*2];
bool dfs(int x)
{
if(mark[x^1]) return false;
if(mark[x]) return true;
mark[x]=true;
S[c++]=x;
for(int i=0;i<G[x].size();i++)
if(!dfs(G[x][i])) return false;
return true;
}
void init(int n)
{
this->n = n;
for(int i=0;i<2*n;i++) G[i].clear();
memset(mark,0,sizeof(mark));
}
void add_clause(int x,int xval,int y,int yval)
{
x=x*2+xval;
y=y*2+yval;
G[x].push_back(y);
}
bool solve()
{
for(int i=0;i<2*n;i+=2)
if(!mark[i] && !mark[i+1])
{
c=0;
if(!dfs(i))
{
while(c>0) mark[S[--c]]=false;
if(!dfs(i+1)) return false;
}
}
return true;
}
}TS;
bool ok(int mid)
{
TS.init(n);
for(int i=0;i<mid;i++)
{
if(c[i]==0)
{
TS.add_clause(a[i],0,b[i],1);
TS.add_clause(b[i],0,a[i],1);
}
else if(c[i]==1)
{
TS.add_clause(a[i],0,b[i],0);
TS.add_clause(a[i],1,b[i],1);
TS.add_clause(b[i],0,a[i],0);
TS.add_clause(b[i],1,a[i],1);
}
else if(c[i]==2)
{
TS.add_clause(a[i],1,b[i],0);
TS.add_clause(b[i],1,a[i],0);
}
}
return TS.solve();
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
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;
while(R>L)
{
int mid = L+(R-L+1)/2;
if(ok(mid)) L=mid;
else R=mid-1;
}
printf("%d\n",L);
}
return 0;
}
分享到:
相关推荐
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
第一章 功能简介本章介绍HDU-EID-V2开发板的功能,使大家对该开发板的功能及特点有个基本了解。1. 处理器( MCU)HDU-EID-V2 开发板的处理器
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
很适合ACM初学者的文档, 题目,代码,解体思路一应俱全
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
1、开发板外观说明 2、电源供电 3、连接调试方法 4、复用功能选择说明
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
教程来自HDU 的ACM教案,非常好的一个资料
教程来自HDU 的ACM教案,非常好的一个资料
语言:中文 (简体) 身在杭电必用的Chrome插件! HDU-GO是一款适用于杭州电子科技大学选课系统的Chrome拓展程序,具有自动抢课、自动学评教、自动计算学分功能。
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
HDU 里面的2000~2099道题目的源码。谢谢支持
ACM题库,一些题目和答案,以及解题报告,传上来共享