`
digiter
  • 浏览: 120383 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

DLX hust 1017

    博客分类:
  • ICPC
阅读更多
“精确覆盖”问题
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#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 = 1005 * 105;
const int maxint = 0x3f3f3f3f;
int L[max_size], R[max_size], U[max_size], D[max_size], CH[max_size], RH[max_size];
int S[1005], O[1005];
int head, size;

void remove(const int &c) {
	//remove column c and all row i that A[i][c] == 1
	L[R[c]] = L[c];
	R[L[c]] = R[c];
	//remove column c;
	for (int i = D[c]; i != c; i = D[i]) {
	//remove i that A[i][c] == 1
		for (int j = R[i]; j != i; j = R[j]) {
			U[D[j]] = U[j];
			D[U[j]] = D[j];
			--S[CH[j]];
			//decrease the count of column C[j];
		}
	}
}
void resume(const int &c) {
	for (int i = U[c]; i != c; i = U[i]) {
		for (int j = L[i]; j != i; j = L[j]) {
			++S[CH[j]];
			U[D[j]] = j;
			D[U[j]] = j;
		}
	}
	L[R[c]] = c;
	R[L[c]] = c;
}
int len;
bool dfs(const int &k) {
	//cout << "new DFS" << endl;
	if (R[head] == head) {
		//One of the answers has been found.
		return true;
	}
	int s(maxint), c;
	//out(head);
	for (int t = R[head]; t != head; t = R[t]) {
		//out(t); out(R[t]);
		//select the column c which has the fewest number of element.
		if (S[t] < s) {
			s = S[t];
			c = t;
		}
	}
	//cout << "remove " << c << endl;
	remove(c);
	for (int i = D[c]; i != c; i = D[i]) {
		O[k] = i; //record the answer.
		len = k;
		for (int j = R[i]; j != i; j = R[j]) {
			remove(CH[j]);
		}
		if (dfs(k + 1)) {
			return true;
		}
		for (int j = L[i]; j != i; j = L[j]) {
			resume(CH[j]);
		}
	}
	resume(c);
	return false;
}
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++;
}
void init(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 main()
{
	int N, M, cnt;
	while (scanf("%d%d", &N, &M) != EOF)
	{
		init(M);
		for (int i = 1; i <= N; ++i) {
			scanf("%d", &cnt);
			int row = -1;
			while (cnt--) {
				int j;
				scanf("%d", &j);
				CH[size] = j, ++S[j];
				if (row == -1) {
					row = node(U[CH[j]], CH[j], size, size);
					RH[row] = i;
				} else {
					int k = node(U[CH[j]], CH[j], L[row], row);
					RH[k] = i;
				}
			}
		}
		//out("DFS");
		bool ans = dfs(1);
		if (ans) {
			printf("%d", len);
			for (int i = 1; i <= len; ++i)
				printf(" %d", RH[O[i]]);
			printf("\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}
分享到:
评论

相关推荐

    DLX.zip_DLX

    3. hust-1017.cpp:这个文件名暗示它可能是华中科技大学(HUST)在线评测系统的一个问题的解决方案。尽管具体问题内容未知,但根据文件名,我们可以推测这同样是一个需要用到高效搜索的题目,DLX算法的引入可能是...

    dlx指令 DLX Instruction Set Architecture

    DLX是一种32位精简指令集计算机(RISC)架构,其特点是可以仅用三种指令格式来管理。DLX的核心是一个固定的定点单元(FXU),并且它还包括一个浮点数扩展。DLX指令集架构主要由以下几个知识点组成: 1. DLX架构基础...

    dlx.zip_DLX_cpu dlx_dlx c++_vhdl_vhdl dlx

    标题中的"dlx.zip_DLX_cpu dlx_dlx c++_vhdl_vhdl dlx"表明这个压缩包主要涉及的是DLX处理器相关的项目,其中包括CPU的设计、编程以及VHDL代码实现。DLX是一种简单的RISC(精简指令集计算机)架构,常用于教学和实验...

    DLX汇编器模拟器

    **DLX汇编器模拟器**是一款专为学习和测试DLX指令集设计的实用工具。DLX(Davis Little eXtended)是RISC(精简指令集计算机)架构的一种,由计算机科学家David A. Patterson教授提出,常用于教学目的,让学生了解...

    mips-dlx模拟器

    "MIPS-DLX模拟器"是一款基于Java编程语言开发的计算机体系结构教学工具,主要用于模拟DLX处理器的工作原理。DLX(Dense Logic eXtended)是计算机体系结构领域中一个简化的RISC(Reduced Instruction Set Computer)...

    LPE-DLX 经典

    【LPE-DLX 经典】是一款深受IT专业人员喜爱的工具集合,它主要用于系统维护、故障排查和性能优化。LPE-DLX的名字来源于“Linux Penetration and Exploitation Deluxe”的缩写,虽然其名称暗示了它可能与黑客攻击和...

    DLX.rar_DLX_dlx文件

    DLX是一种特定的指令集架构(ISA),它主要用于教学和研究目的,以帮助理解计算机系统设计的基本原理。DLX是由计算机科学家David A. Patterson和John L. Hennessy设计的,作为他们教材《计算机体系结构:量化方法》...

    DLX.zip_DLX_dlx算法

    **DLX算法详解** DLX( Dancing Links )算法,由计算机科学家Donald Knuth提出,是一种在图论中用于解决完全多对一匹配问题的高效算法。它在回溯搜索中展现出优秀的性能,尤其适用于解决0-1背包、 Exact Cover 和...

    DLX模拟器DlxSimulator.rar

    **DLX模拟器DlxSimulator** DLX模拟器DlxSimulator是一款专门用于执行基于DLX指令集架构的汇编程序的软件工具。DLX是计算机体系结构中的一种简化模型,由计算机科学家David A. Patterson教授设计,常用于教学和研究...

    计算机体系结构dlx实验报告

    在研究计算机体系结构的实验中,DLX(Digital-Logic eXperiment)实验报告为我们提供了一系列关于使用DLX汇编语言编程的实践内容和分析。DLX是一种教学用的简化精简指令集计算机(RISC)处理器的架构,常用于计算机...

    dlx.zip_DLX_MIPS_dlx cpu pipelin

    标题中的“dlx.zip_DLX_MIPS_dlx cpu pipelin”指的是一个关于DLX处理器的MIPS流水线实现的压缩包文件。这个压缩包可能包含了罗晓华同学完成的一个DLX处理器模拟器,用于理解MIPS架构下的指令流水线工作原理。 首先...

    比较好用的DLX模拟器

    标题“比较好用的DLX模拟器”指的是一个针对MIPS DLX架构设计的模拟器,该模拟器在功能性和易用性上具有一定的优势。描述中的“大作业写的”可能意味着这是一个学术项目或者课程作业,表明作者在完成这个模拟器时...

    DLX.zip_DLX_体系仿真_开发DLX

    《DLX体系仿真与开发详解》 在计算机科学领域,体系结构仿真是一种重要的技术,它允许我们模拟和分析特定的处理器架构,以便于理解和优化其性能。本文将深入探讨DLX处理器的实现,以及如何利用Visual C++进行体系...

    DLX 模拟器及教程

    《DLX模拟器及教程》是一份专注于计算机系统结构、体系设计和实验模拟技术的教育资源。DLX是一种简化版的RISC(精简指令集计算机)架构,常用于教学和研究,让学生能深入理解计算机底层的工作原理。TMS320F2812是一...

    DLX指令集(汇编)

    "DLX指令集(汇编)" DLX指令集是computer science中非常重要的一部分,深入了解DLX指令集对了解汇编语言有很大的帮助。本文档将对DLX指令集进行详细的介绍,包括指令集的组成、寄存器的使用、立即数的表示方式等。...

    DLX处理器浮点数流水线性能的研究.pdf

    ### DLX处理器浮点数流水线性能的研究 #### 一、引言 DLX处理器作为一种虚拟的32位微处理机系统结构,在计算机系统结构的教学和研究领域具有重要的地位。由John L. Hennessy(斯坦福大学)和David A. Patterson...

    dlx语言写的求和

    dlx语言写的求和运算,计算机系统结构试验

    DLX_Links_DLX_

    标题中的"DLX_Links_DLX_"暗示了我们讨论的主题是关于一种名为"Dancing Links"(跳舞链)的算法,通常简称为DLX。这个算法是由Donald Knuth提出的一种高效解决完全背包问题、数独问题和其他一系列组合优化问题的方法...

    windlx模拟器 and DLX实验指导书.pdf

    《风铃DX(WindLX)模拟器与DLX处理器实验指南》 本文将深入探讨风铃DX(WindLX)模拟器以及与其相关的DLX处理器实验。DLX处理器是一种教学用的精简指令集计算机(RISC)架构,由计算机科学家David A. Patterson...

    LordPE DLX增强豪华版

    LordPE DLX增强豪华版 (1) 为LordPE查看输入表部分加上搜索功能 (2) 为LordPE查看输入表部分加右键菜单(仅复制ThunkRVA/FirstThunk列). (3) 当点击LordPE查看输入表部分中"View always FirstThunk",保持光条在原来...

Global site tag (gtag.js) - Google Analytics