- 浏览: 118411 次
- 性别:
- 来自: 北京
最新评论
“精确覆盖”问题
#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; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1153/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 840线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 850线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 888写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 972转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1188封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 798终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 602写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1138源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 804import java.util.*; import j ... -
整数划分
2010-10-07 10:38 840#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 980// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1050typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1134最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1292Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 775static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 878标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hdu 3498
2010-08-11 16:48 1041“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1004推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ... -
RMQ模板
2010-07-28 11:04 1187/* * Author: rush * Creat ...
相关推荐
DLX Instruction Set Architecture
一款很好用的DLX汇编器,链接器,模拟dlx环境,win7下可视
这是一个用java写得dlx模拟器,实现了流水线和解决相关
DLX CPU VHDL CODE UNIVERSITY
学习使用 DLX 汇编语言编程,进一步分析相关现象。 二、实验设备环境 DLX 汇编语言环境 三、实验内容和要求 自编一段汇编代码,完成一维向量加法运算,并输出结果。观察程序中出现的数据/控 制/结构相关。(注:使用...
dlx语言写的求和运算,计算机系统结构试验
LordPE DLX增强豪华版 (1) 为LordPE查看输入表部分加上搜索功能 (2) 为LordPE查看输入表部分加右键菜单(仅复制ThunkRVA/FirstThunk列). (3) 当点击LordPE查看输入表部分中"View always FirstThunk",保持光条在原来...
DLX指令集实现程序,将汇编代码转换成二进制代码写入文件中。
DLX算法,是由Knuth提出的一种在图论中图遍历的一种高效算法。
用于修改H1、H2步步高学习机内部DLX文件内的图片,从而达到修改学习机内部程序图片显示的效果
DLX用于高效率搜索,是一种覆盖问题模型的算法。DLX利用了双向链表,体现了数据结构的美。
DLX流水线指令调度,测试指令调度对系统性能的影响。包括实验过程,截图,实验原理和改进方法等,供同学们参考。蔡老师的学生你们懂的。
大作业写的MIPS DLX的模拟器 应该是比较好用的。。
(1) 为LordPE查看输入表部分加上搜索功能 (2) 为LordPE查看输入表部分加右键菜单(复制ThunkRVA/FirstThunk列). (3) 当点击LordPE查看输入表部分中"View always FirstThunk",保持光条在原来位置.(LordPE默认会将光条...
windlx模拟器 DLX实验指导书windlx模拟器 DLX实验指导书
DLX处理器浮点数流水线性能的研究.pdf关于DLX的参考文献
A VHDL implementation DLX processor
这些指令既没有出现在Hennessy 和 Patterson的课本中,也没有列在Sailer 和 Kaeli 合编的"The DLX Instruction Set Architecture Handbook"一书中。新的指令是:sgeu, sgtu, sleu, sltu -- all compares using ...
DLX实现,实用Visual C++编程,思想为MIPS体系结构,可以考察系统仿真的性能和指标
懂得不用多介绍了把,下载享用吧