大家好，又见面了，我是全栈君，今天给大家准备了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;}
版权声明：本文博主原创文章，博客，未经同意不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116968.html原文链接：https://javaforall.net
