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)


相关推荐

  • android 4怎么打开usb调试?「建议收藏」

    android 4怎么打开usb调试?「建议收藏」手机连接电脑,刷机,等都需要打开手机USB调试模式,你才能进行操作的。所以买了手机建议都要打开这个USB调试,手机锁屏密码忘记也需要打开这个。这个比较重要。工具/原料手机安卓android系统方法/步骤打开自己的手机找到《设置》点击,进入以下图例。在点击《关于手机》

  • Swift的属性,方法,下标脚本以及继承

    Swift的属性,方法,下标脚本以及继承

    2021年12月16日
  • bat批处理 for循环_批处理 for /f

    bat批处理 for循环_批处理 for /f一、前言在批处理中,for是最为强大的命令语句,它的出现,使得解析文本内容、遍历文件路径、数值递增/递减等操作成为可能;配合if、call、goto等流程控制语句,更是可以实现脚本复杂的自动化、智能化操作;合理使用for语句,还能使代码大为简化,免除各位编写大量重复语句之苦。二、for语句的基本用法1、举例:正如色彩缤纷的七彩光芒是由红绿蓝三原色构成的一样,最复杂的for语句,也…

  • docker启动mysql报错_mysql查看root密码

    docker启动mysql报错_mysql查看root密码dockerrun–name=mediawiki_mysql\-eMYSQL_DATABASE=wikidb\-eMYSQL_USER=wikiuser\-eMYSQL_PASSWORD=mysecret\-eMYSQL_ROOT_PASSWORD=zhang123\-v/var/mediawiki/mysql:/var/lib/mysql\-dmysql:5.7启动…

  • 纸的大小图解_常用纸张尺寸及示意图(A0,A1A3,A4,A5A8)数据源维基百科.PDF

    纸的大小图解_常用纸张尺寸及示意图(A0,A1A3,A4,A5A8)数据源维基百科.PDF常用纸张尺寸及示意图(A0,A1A3,A4,A5A8)数据源维基百科mFPCharging-常用纸张尺寸说明2011-12-09v2.0常用纸张尺寸及示意图(A0,A1…A3,A4,A5…A8)数据源:维基百科标准定义ISO216定义了A、B、C三个系列的纸张尺寸。C系列纸张尺寸主要使用于信封。ISO216的格式遵循着的比率;放在一起的两张纸有着…

  • 如何取消计算机用户名,Win10如何取消登录界面显示用户名?「建议收藏」

    如何取消计算机用户名,Win10如何取消登录界面显示用户名?「建议收藏」Win10如何取消登录界面显示用户名?求之不得,梦寐思服。得到之后,不过尔尔!不知道您为什么求Win10取消登录界面显示用户名的操作方法,个人感觉,结果很令人不习惯。还不如改成直接登陆系统呢!既然搜索,必然有用,希望下面内容能令您满意。第一步、按Win+R组合键,呼出运行命令输入框,输入regedit后按回车键温馨提示:如果出现用户账户控制提示窗口,点击“是”即可第二步、在注册表编辑器窗口,依次展…

发表回复

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

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