Tag Archives: 哈密顿路

hihoCoder 1087 & week 63-1-Hamiltonian Cycle

Leave a reply

hihoCoder 1087 & week 63-1-Hamiltonian Cycle #1087 : Hamiltonian Cycle 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Given a directed graph containing n vertice (numbered from 1 to n) and m edges. Can you tell us how many different Hamiltonian Cycles are there in this graph? A Hamiltonian Cycle is a cycle that starts from some vertex, visits each vertex (except for the start vertex) exactly once, and finally ends at the start vertex. Two Hamiltonian Cycles C1, C2 are different if and only if there exists some vertex i that, the next vertex of vertex i in C1 is different from the next vertex of vertex i in C2. 输入 The first line contains two integers n and m. 2 <= n <= 12, 1 <= m <= 200. Then follows m line. Each line contains two different integers a and b, indicating there is an directed edge from vertex a to vertex b. 输出 Output an integer in a single line — the number of different Hamiltonian Cycles in this graph. 提示 额外的样例:

样例输入 样例输出
3 3 1 2 2 1 1 3 0
样例输入 4 7 1 2 2 3 3 4 4 1 1 3 4 2 2 1 样例输出 2
本题要求解一个有向图中存在多少个哈密顿回路，因为本题的n不超过12，所以可以暴力求解，但是可以用位运算和记忆化搜索提高搜索速度。 常规思路是从某一点DFS，计算所有哈密顿回路的数量，伪代码如下： [cpp] DFS(int nowVertex, bool visitedVertex, int path, int length) visitedVertex[ nowVertex ] = True; If (all Vertex is visited) Then Count = Count + 1 Else For (u is next vertex of nowVertex) If (not visitedVertex[ u ]) Then path[ length ] = u DFS(u, visitedVertex, path, length + 1) End If End For End If visitedVertex[ nowVertex ] = False [/cpp] 位运算的思路是用变量unused的二进制位表示一个点是否访问过，1未访问，0访问了。所以当DFS到unused==0时，找到一条哈密顿路径，如果该路径的终点能回到起点（默认为1），则构成一条哈密顿回路。部分代码如下： [cpp] const int MAXN = 14; int edge[ MAXN ];//edge[i]二进制中1的序号表示i能访问的节点编号 int p[1 << MAXN];//p[1<<i]=i+1表示只有i点访问了的情况为1<<i int cnt; void dfs(int nowVertex, int unused) { if (!unused) {//所有节点访问完了 cnt += (edge[nowVertex] & 1);//判断能否回到起始节点1 return ; } int rest = unused & edge[ nowVertex ];//剩余的能访问到的未访问节点 while (rest) { int tp = rest & (-rest);//依次取出可访问节点 dfs(p[ tp ], unused – tp);//访问 rest -= tp; } return ; } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) p[ 1 << i ] = i + 1; while (m–) { int u, v; scanf("%d %d", &u, &v); edge[u] |= 1 << (v – 1);//记录u能访问节点的情况 } dfs(1, (1 << n) – 2);//初始的时候访问了1号节点，所以-1-1=-2 printf("%d\n", cnt); return 0; } [/cpp] 这一版本的代码简洁易懂，效率也还可以，用时558MS，内存0MB。 但是还可以改进，在DFS过程中可能遇到某个节点的多次unused相同的情况，此时后面几次的DFS都是没有必要的，可以剪枝。 设f[i][j]为当前访问节点为i，已经访问过的节点情况为j时的方案数，则哈密顿路径的情况数为f[i][0]，i在[1,n]，哈密顿回路的情况数就是把所有i能回到1的f[i][0]情况数加起来。 那么怎么来计算f[i][j]呢，需要按照状态中1的个数来枚举，伪代码如下： [cpp] For numberOfOnes = n-1 .. 0 For (unused | the number of ones of unused equals numberOfOnes) For nowVertex = 1 .. n For prevVertex = 1 .. n If (unused & (1 << (nowVertex – 1)) == 0) and (prevVertex != nowVertex) and (edge[ prevVertex ] & (1 << (nowVertex – 1)) != 0) Then f[ nowVertex ][ unused ] = f[ nowVertex ][ unused ] + f[ prevVertex ][unused + (1 << (nowVertex – 1))] End If End For End For End For End For [/cpp] 第二层for循环中的unused就是所有“在n位二进制中设置numberOfOnes位1”的所有状态，最内层的if判断该状态必须满足1)已经访问了当前节点2)前驱节点不等于当前节点3)前驱节点有到当前节点的边，则f[当前节点][访问情况为unused]+=f[前驱节点][访问情况为unused+还没访问当前节点]。 详细分析可以看官方题解。完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> #include<iterator> using namespace std; const int MAXN = 14; int edge[MAXN]; int p[1 << MAXN]; int f[MAXN][1<<MAXN]; //n位二进制中出现k个1的所有排列情况 vector<int> dfs(int n, int k) { if (k == 0)//出现0个1，只有一种情况，全0 return vector<int>(1, 0); else { //********** n==k的情况 ************************** vector<int> r = dfs(n – 1, k – 1);//n-1位中出现k-1个1//将大问题分解成小问题 for (int &i : r) { i |= (1 << (n – 1));//补上第n位也为1 } //************************************************** if (n > k) { vector<int> t = dfs(n – 1, k);//此时第n位可以为0 copy(t.begin(), t.end(), back_inserter(r)); } return r; } } int main() { //freopen("input.txt", "r", stdin); int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) p[1 << i] = i + 1; while (m–) { int u, v; scanf("%d %d", &u, &v); edge[u] |= 1 << (v – 1); } f[1][(1 << n) – 2] = 1; for (int numberOfOnes = n – 1; numberOfOnes >= 0; numberOfOnes–) { vector<int> stat = dfs(n, numberOfOnes); for (int i = 0; i < stat.size(); i++) { int s = stat[i]; for (int nowVertex = 1; nowVertex <= n; nowVertex++) { for (int prevVertex = 1; prevVertex <= n; prevVertex++) { if ((s & (1 << (nowVertex – 1))) == 0 && prevVertex != nowVertex && (edge[prevVertex] & (1 << (nowVertex – 1))) != 0) f[nowVertex][s] += f[prevVertex][s | (1 << (nowVertex – 1))]; } } } } int cnt = 0; for (int i = 1; i <= n; i++) if (edge[i] & 1) cnt += f[i][0]; printf("%d\n", cnt); return 0; } [/cpp] 本代码提交AC，用时21MS，内存0MB，相比于上一版本，速度提升了一个数量级。]]>

HDOJ 5424-Rikka with Graph II

Leave a reply

HDOJ 5424-Rikka with Graph II Rikka with Graph II Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 379 Accepted Submission(s): 94 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: Yuta has a non-direct graph with n vertices and n edges. Now he wants you to tell him if there exist a Hamiltonian path. It is too difficult for Rikka. Can you help her? Input There are no more than 100 testcases. For each testcase, the first line contains a number n(1≤n≤1000). Then n lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. Output For each testcase, if there exist a Hamiltonian path print “YES” , otherwise print “NO”. Sample Input 4 1 1 1 2 2 3 2 4 3 1 2 2 3 3 1 Sample Output NO YES Hint For the second testcase, One of the path is 1->2->3 If you doesn’t know what is Hamiltonian path, click here (https://en.wikipedia.org/wiki/Hamiltonian_path). Source BestCoder Round #53 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422

这题题意很明确，判断一个无向图中是否存在哈密顿路径，注意不是哈密顿回路。
由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次，形成的路径称为哈密顿路径，闭合的哈密顿路径称作哈密顿回路，含有哈密顿回路的图称为哈密顿图。
本来判断一个常规图中是否存在哈密顿路径是NP完全问题，不可能有多项式解，所以如果依次对每个点DFS，肯定超时。 但是这题很特殊，图中只有n个点，n条边！如果存在哈密顿路径L，则路径长度为n-1条边，设L两个端点为A,B，此时还剩下一条边a，这条边有三种情况： 1）a在L的内部连接，这时A,B的度数都为1，其他点的度数为2或3； 2）a一端在A（或B），另一端在L的内部，这时L的另一个端点B（或A）的度数为1，其他点的度数为2或3； 3）a连接了A,B，此时所有点的度数都为2。 如果存在哈密顿路径，这三种情况下，L的某个端点的度数都是最少的。所以可以先找到度数最小的点，再从这个点开始DFS，这样只需要一次DFS就可以判断是否存在哈密顿路径。 当然要先判断这个图是否连通，我起初使用了并查集，但是超时，郁闷。后来发现，如果哈密顿路径存在，则肯定连通，且此时读数为1点不超过2个，所以可以用这个条件判断是否连通。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> using namespace std; const int kMaxN = 1005; int degree[kMaxN]; vector<vector<int>> path; int visit[kMaxN]; int n, done; bool DFS(int s) { done++; visit[s] = 1; if (done == n) return true; int v; for (int i = 0; i < path[s].size(); i++) { v = path[s][i]; if (!visit[v]) { if (DFS(v)) return true; } } done–; visit[s] = 0; return false; } bool CheckHamiltonian() { int min_degree = n + 1, bad_node_num = 0, id; for (int i = 1; i <= n; i++) { if (degree[i] && degree[i] < min_degree) { min_degree = degree[i]; id = i; } if (degree[i] <= 1) bad_node_num++; } if (bad_node_num > 2) return false; memset(visit, 0, sizeof(visit)); done = 0; return DFS(id); } int main() { //freopen("input.txt", "r", stdin); while (~scanf("%d", &n)) { memset(degree, 0, sizeof(degree)); path.clear(); path.resize(n + 1); int u, v; for (int i = 0; i < n; i++) { scanf("%d %d", &u, &v); if (u == v) continue; degree[u]++; degree[v]++; path[u].push_back(v); path[v].push_back(u); } if (CheckHamiltonian()) printf("YES\n"); else printf("NO\n"); } return 0; } [/cpp] 本代码提交AC，用时93MS，内存1800K。]]>