大家好,又见面了,我是全栈君,今天给大家准备了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账号...