HDU 3715 Go Deeper(2-sat)

HDU 3715 Go Deeper(2-sat)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

HDU 3715 Go Deeper

题目链接

题意:依据题意那个函数,构造x数组。问最大能递归层数

思路:转化为2-sat问题,因为x仅仅能是0。1,c仅仅能是0,1。2那么问题就好办了,对于0, 1, 2相应各自是3种表达式,然后二分深度,搞2-sat就可以

代码:

#include <cstdio>#include <cstring>#include <cstdlib>#include <vector>#include <algorithm>using namespace std;const int MAXNODE = 205;struct TwoSet {	int n;	vector<int> g[MAXNODE * 2];	bool mark[MAXNODE * 2];	int S[MAXNODE * 2], sn;	void init(int tot) {		n = tot * 2;		for (int i = 0; i < n; i += 2) {			g[i].clear();			g[i^1].clear();		}		memset(mark, false, sizeof(mark));	}	void add_Edge(int u, int uval, int v, int vval) {		u = u * 2 + uval;		v = v * 2 + vval;		g[u^1].push_back(v);		g[v^1].push_back(u);	}	void delete_Edge(int u, int uval, int v, int vval) {		u = u * 2 + uval;		v = v * 2 + vval;		g[u^1].pop_back();		g[v^1].pop_back();	}	bool dfs(int u) {		if (mark[u^1]) return false;		if (mark[u]) return true;		mark[u] = true;		S[sn++] = u;		for (int i = 0; i < g[u].size(); i++) {			int v = g[u][i];			if (!dfs(v)) return false;		}		return true;	}	bool solve() {		for (int i = 0; i < n; i += 2) {			if (!mark[i] && !mark[i + 1]) {				sn = 0;				if (!dfs(i)){					for (int j = 0; j < sn; j++)						mark[S[j]] = false;					sn = 0;					if (!dfs(i + 1)) return false;				}			}		}		return true;	}} gao;const int N = 10005;int t, n, m;int a[N], b[N], c[N];bool judge(int dep) {	gao.init(n);	for (int i = 0; i < dep; i++) {		if (c[i] == 0)			gao.add_Edge(a[i], 1, b[i], 1);		else if (c[i] == 1) {			gao.add_Edge(a[i], 0, a[i], 1);			gao.add_Edge(a[i], 0, b[i], 1);			gao.add_Edge(b[i], 0, a[i], 1);			gao.add_Edge(b[i], 0, b[i], 1);		} else			gao.add_Edge(a[i], 0, b[i], 0);	}	return gao.solve();}int main() {	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 + 1;		while (l < r) {			int mid = (l + r) / 2;			if (judge(mid)) l = mid + 1;			else r = mid;		}		printf("%d\n", l - 1);	}	return 0;}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116968.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • armv7在哪儿看(armv7s)

    iOS中的armv7,armv7s,arm64,i386,x86_64都是什么在做静态库的时候以及引用静态库的时候经常会遇到一些关于真机模拟器不通用的情况,会报错找不到相应库导致编译失败,这里简单记录一下各种设备支持的架构。iOS测试分为模拟器测试和真机测试,处理器分为32位处理器,和64位处理器,模拟器32位处理器测试需要i386架构,(iphone5,iphone5s以下的模拟器…

  • linux rm 命令详解,Linux rm命令使用指南「建议收藏」

    linux rm 命令详解,Linux rm命令使用指南「建议收藏」Linux系统的众多命令中,rm命令主要用于删除文件,下面小编就来详解介绍下Linux系统的rm命令,希望对初学者有一定的帮助。名称:rm使用权限:所有使用者使用方式:rm[options]name.。。说明:删除档案及目录。参数:?-i删除前逐一询问确认。-f即使原档案属性设为唯读,亦直接删除,无需逐一确认。-r将目录及以下之档案亦逐一删除。范例:删除所有C语言程式档;删除前逐一询问确…

    2022年10月29日
  • installous下载ipa目录

    installous下载ipa目录/private/var/mobile/Documents/Installous/Downloads

  • 深度剖析原理!java培训网课代理[通俗易懂]

    深度剖析原理!java培训网课代理[通俗易懂]前言想必很多人在为接下来的金九银十做准备,或许你只是想找到一份工作,亦或许你希望通过今年最后这波拿到一个理想的工作和薪酬。不管是哪一种情况,你都需要提前做好准备,而不是临时抱佛脚。LZ为大家分享的这些面试真题一定要基于自己的技术栈来思考,而不是背一下就觉得这个我会了。试想一下,如果面试官接着往深处问,你能保证自己回答的上来吗?这样的跳槽方式在以前或许还比较适用,但是在今年一定是没有效果的,没有意义的。LZ把这350道Java面试真题分成了五大专题,分别是:性能优化、微服务架构、并发编程(高级)、开源框

  • Python注释以及快捷键「建议收藏」

    Python注释以及快捷键「建议收藏」1、单行注释单行注释是#Mac的快捷键是command+/windows的快捷键是Ctrl+/2、多行注释多行注释是三个单引号'''注释'&#39

  • 微信 开发诡异的40029错误invalid code错误 443 failed to respond错误的解决办法

    微信 开发诡异的40029错误invalid code错误 443 failed to respond错误的解决办法情景:使用静默授权或感知授权的方式将请求绑定到微信公众号的菜单栏上。链接如下:https://open.weixin.qq.com/connect/oauth2/authorize?appid=APPID&redirect_uri=REDIRECT_URI&response_type=code&scope=SCOPE&state=STATE#wechat_redirect 当点击菜单按钮时微信

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号