hdu4421-Bit Magic(2-SAT)
2023-03-14 09:48:59 时间
题意
根据图中公式由A[]构造B[][],现在给你B,问你存不存在一个数组A使之成立。
题解:对于每一位进行2-sat求解。
比赛半个小时时间,没做出来……
一直T。
因为本身对算法不确定,所以也不知道怎么办
赛后才发现是数组开小了、、、、
真坑啊。。。
#include <bits/stdc++.h> using namespace std; const int N = 1005; int a[N], b[N][N]; struct Edge { int from, to, next; } edge[N*N*4]; int head[N], cntE; void addedge(int u, int v) { edge[cntE].from = u; edge[cntE].to = v; edge[cntE].next = head[u]; head[u] = cntE++; } int dfn[N], low[N], idx; int stk[N], top; int in[N]; int kind[N], cnt; void tarjan(int u) { dfn[u] = low[u] = ++idx; in[u] = true; stk[++top] = u; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if (in[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { ++cnt; while (1) { int v = stk[top--]; kind[v] = cnt; in[v] = false; if (v == u) break; } } } int opp[N], ind[N], col[N]; bool topsort(int n) { for (int i = 0; i < 2*n; ++i) { if (!dfn[i]) tarjan(i); } for (int i = 0; i < n; ++i) { int k1 = kind[i], k2 = kind[i+n]; if (k1 == k2) return false; } return true; } void init() { cntE = 0; memset(head, -1, sizeof head); memset(dfn, 0, sizeof dfn); memset(in, false, sizeof in); idx = top = cnt = 0; memset(ind, 0, sizeof ind); memset(col, 0, sizeof col); } int main() { //freopen("in.txt", "r", stdin); int n; while (~scanf("%d", &n)) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &b[i][j]); } } bool fg = true; for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { if (i == j) { if (b[i][j] != 0) { fg = false; break; } } else if (b[i][j] != b[j][i]) { fg = false; break; } } if (!fg) break; } if (!fg) { printf("NO\n"); continue; } for (int w = 0; w <= 30; ++w) { init(); int cnt = 0; for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { //if (i == j) continue; if (i % 2 == 0 && j % 2 == 0) { if (b[i][j] & (1 << w)) { addedge(i, i+n); addedge(j, j+n); } else { addedge(j+n, i); addedge(i+n, j); } } else if (i % 2 == 1 && j % 2 == 1) { if (b[i][j] & (1 << w)) { addedge(j, i+n); addedge(i, j+n); } else { addedge(i+n, i); addedge(j+n, j); } } else { if (b[i][j] & (1 << w)) { addedge(i, j+n); addedge(j, i+n); addedge(j+n, i); addedge(i+n, j); } else { addedge(i, j); addedge(j, i); addedge(i+n, j+n); addedge(j+n, i+n); } } } } if (!topsort(n)) { fg = false; break; } } if (fg) printf("YES\n"); else printf("NO\n"); } return 0; }
相关文章
- Tampermonkey配合IDM实现网盘不限速
- google、YouTube、Medium进度条
- 如何避免内存溢出和频繁的垃圾回收
- 推荐一款文本编辑器的主题
- 【愚公系列】2023年01月 .NET CORE工具案例-LazyCaptcha图片验证码
- Docker 命令集锦
- 过度设计有意义吗
- 六问Nerf | 简单易懂的神经辐射场入门介绍
- 大厂怎么做Code Review?
- 使用 Excel cdata addmin 连接 SAP ABAP 系统时需要填写的参数定义解释
- 国际版抖音tiktok,用户量从15亿20亿,覆盖150多个国家
- Meta分析森林图中文显示问题
- ECCV 2022 | 基于点云累积的动态三维场景分析
- 一本修炼秘籍,带你打穿文件上传的21层妖塔(1)
- 高德地图不同层级是否显示文字记录
- 在不同环境下 Docker 的安装部署
- vue.js客服系统实时聊天项目开发(三)实现对话框聊天界面
- Parallels Desktop安装序列号破解激活教程
- 继承是代码复用的最佳方案吗?
- 振弦采集模块配置工具VMTool的常见功能