- 浏览: 118408 次
- 性别:
- 来自: 北京
最新评论
“多重覆盖”或“重复覆盖”问题
#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 1152/** * @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 887写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]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 hust 1017
2010-08-11 16:50 848“精确覆盖”问题 #include <cstdio& ... -
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体系结构,可以考察系统仿真的性能和指标
懂得不用多介绍了把,下载享用吧