- 浏览: 120734 次
- 性别:
- 来自: 北京
最新评论
“多重覆盖”或“重复覆盖”问题
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #define out(v) cout << #v << ": " << (v) << endl using namespace std; typedef long long LL; const int max_size = 60 * 60; const int maxint = 0x3f3f3f3f; int L[max_size], R[max_size], U[max_size], D[max_size], CH[max_size]; int S[60]; int head, size; void remove(const int &c) { for (int i = D[c]; i != c; i = D[i]) { L[R[i]] = L[i], R[L[i]] = R[i]; --S[CH[i]]; } } void resume(const int &c) { for (int i = U[c]; i != c; i = U[i]) { ++S[CH[i]]; L[R[i]] = R[L[i]] = i; } } int H() { int cnt = 0; bool cover[60] = {false}; for (int c = R[head]; c != head; c = R[c]) if (!cover[c]) { cover[c] = true, ++cnt; for (int i = D[c]; i != c; i = D[i]) for (int j = R[i]; j != i; j = R[j]) cover[CH[j]] = true; } return cnt; } int ans, ans_cnt; void dfs(const int &k) { if (R[head] == head) { ans = min(ans, k); return; } int s(maxint), c; for (int t = R[head]; t != head; t = R[t]) { if (S[t] < s) s = S[t], c = t; } for (int i = D[c]; i != c; i = D[i]) { remove(i); for (int j = R[i]; j != i; j = R[j]) remove(j); if (k + 1 + H() < ans) dfs(k + 1); for (int j = L[i]; j != i; j = L[j]) resume(j); resume(i); } } int node(int up, int down, int left, int right) { U[size] = up, D[size] = down; L[size] = left, R[size] = right; D[up] = U[down] = R[left] = L[right] = size; return size++; } bool G[60][60]; void init(int N, int M) { size = 0; head = node(0, 0, 0, 0); for (int j = 1; j <= M; ++j) { node(j, j, L[head], head); CH[j] = j, S[j] = 0; } int u, v; for (int u = 1; u <= N; ++u) { int row = -1; for (int v = 1; v <= N; ++v) { if (!G[u][v]) continue; if (row == -1) { row = node(U[CH[v]], CH[v], size, size); CH[row] = v, ++S[v]; } else { int k = node(U[CH[v]], CH[v], L[row], row); CH[k] = v, ++S[v]; } } } } int main() { int N, M, u, v; while (scanf("%d%d", &N, &M) != EOF) { for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) G[i][j] = (i == j ? true : false); while (M--) { scanf("%d%d", &u, &v); G[u][v] = G[v][u] = true; } init(N, N); ans = maxint; dfs(1); printf("%d\n", ans - 1); } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1189/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 867线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 890线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 944写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 1012转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1223封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 829终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 651写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1175源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 838import java.util.*; import j ... -
整数划分
2010-10-07 10:38 861#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 1012// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1074typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1170最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1339Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 811static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 922标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 881“精确覆盖”问题 #include <cstdio& ... -
hdu 3509
2010-08-09 11:22 1030推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ... -
RMQ模板
2010-07-28 11:04 1224/* * Author: rush * Creat ...
相关推荐
DLX是一种32位精简指令集计算机(RISC)架构,其特点是可以仅用三种指令格式来管理。DLX的核心是一个固定的定点单元(FXU),并且它还包括一个浮点数扩展。DLX指令集架构主要由以下几个知识点组成: 1. DLX架构基础...
标题中的"DLX.zip_DLX"暗示我们关注的是一个与DLX算法相关的压缩包文件,而这个算法主要用于解决高效率的搜索问题。DLX,全称为 Dancing Links(跳舞链),是由日本数学家和计算机科学家Hideo Kojima提出的。这个...
标题中的"dlx.zip_DLX_cpu dlx_dlx c++_vhdl_vhdl dlx"表明这个压缩包主要涉及的是DLX处理器相关的项目,其中包括CPU的设计、编程以及VHDL代码实现。DLX是一种简单的RISC(精简指令集计算机)架构,常用于教学和实验...
**DLX汇编器模拟器**是一款专为学习和测试DLX指令集设计的实用工具。DLX(Davis Little eXtended)是RISC(精简指令集计算机)架构的一种,由计算机科学家David A. Patterson教授提出,常用于教学目的,让学生了解...
"MIPS-DLX模拟器"是一款基于Java编程语言开发的计算机体系结构教学工具,主要用于模拟DLX处理器的工作原理。DLX(Dense Logic eXtended)是计算机体系结构领域中一个简化的RISC(Reduced Instruction Set Computer)...
【LPE-DLX 经典】是一款深受IT专业人员喜爱的工具集合,它主要用于系统维护、故障排查和性能优化。LPE-DLX的名字来源于“Linux Penetration and Exploitation Deluxe”的缩写,虽然其名称暗示了它可能与黑客攻击和...
DLX是一种特定的指令集架构(ISA),它主要用于教学和研究目的,以帮助理解计算机系统设计的基本原理。DLX是由计算机科学家David A. Patterson和John L. Hennessy设计的,作为他们教材《计算机体系结构:量化方法》...
标题“比较好用的DLX模拟器”指的是一个针对MIPS DLX架构设计的模拟器,该模拟器在功能性和易用性上具有一定的优势。描述中的“大作业写的”可能意味着这是一个学术项目或者课程作业,表明作者在完成这个模拟器时...
**DLX算法详解** DLX( Dancing Links )算法,由计算机科学家Donald Knuth提出,是一种在图论中用于解决完全多对一匹配问题的高效算法。它在回溯搜索中展现出优秀的性能,尤其适用于解决0-1背包、 Exact Cover 和...
**DLX模拟器DlxSimulator** DLX模拟器DlxSimulator是一款专门用于执行基于DLX指令集架构的汇编程序的软件工具。DLX是计算机体系结构中的一种简化模型,由计算机科学家David A. Patterson教授设计,常用于教学和研究...
用于修改H1、H2步步高学习机内部DLX文件内的图片,从而达到修改学习机内部程序图片显示的效果
在研究计算机体系结构的实验中,DLX(Digital-Logic eXperiment)实验报告为我们提供了一系列关于使用DLX汇编语言编程的实践内容和分析。DLX是一种教学用的简化精简指令集计算机(RISC)处理器的架构,常用于计算机...
标题中的“dlx.zip_DLX_MIPS_dlx cpu pipelin”指的是一个关于DLX处理器的MIPS流水线实现的压缩包文件。这个压缩包可能包含了罗晓华同学完成的一个DLX处理器模拟器,用于理解MIPS架构下的指令流水线工作原理。 首先...
《DLX体系仿真与开发详解》 在计算机科学领域,体系结构仿真是一种重要的技术,它允许我们模拟和分析特定的处理器架构,以便于理解和优化其性能。本文将深入探讨DLX处理器的实现,以及如何利用Visual C++进行体系...
《DLX模拟器及教程》是一份专注于计算机系统结构、体系设计和实验模拟技术的教育资源。DLX是一种简化版的RISC(精简指令集计算机)架构,常用于教学和研究,让学生能深入理解计算机底层的工作原理。TMS320F2812是一...
"DLX指令集(汇编)" DLX指令集是computer science中非常重要的一部分,深入了解DLX指令集对了解汇编语言有很大的帮助。本文档将对DLX指令集进行详细的介绍,包括指令集的组成、寄存器的使用、立即数的表示方式等。...
### DLX处理器浮点数流水线性能的研究 #### 一、引言 DLX处理器作为一种虚拟的32位微处理机系统结构,在计算机系统结构的教学和研究领域具有重要的地位。由John L. Hennessy(斯坦福大学)和David A. Patterson...
标题中的"DLX_Links_DLX_"暗示了我们讨论的主题是关于一种名为"Dancing Links"(跳舞链)的算法,通常简称为DLX。这个算法是由Donald Knuth提出的一种高效解决完全背包问题、数独问题和其他一系列组合优化问题的方法...
dlx语言写的求和运算,计算机系统结构试验
《风铃DX(WindLX)模拟器与DLX处理器实验指南》 本文将深入探讨风铃DX(WindLX)模拟器以及与其相关的DLX处理器实验。DLX处理器是一种教学用的精简指令集计算机(RISC)架构,由计算机科学家David A. Patterson...