首页 > ACM题库 > HDU-杭电 > HDU 3200-Arborescence Counting-动态规划-[解题报告]HOJ
2014
03-06

HDU 3200-Arborescence Counting-动态规划-[解题报告]HOJ

Arborescence Counting

问题描述 :

"In graph theory, an arborescence is a directed graph in which, for a vertex v called the root and any other vertex u, there is exactly one directed path rom v to u. In other words, an arborescence is a directed, rooted tree in which all edges point away from the root. Every arborescence is a directed acyclic graph."– from Wikipedia, the free encyclopedia

You are given a directed graph with N vertices, and your task is to count the number of different arborescences of size N that can be found in the given graph.

Two arborescences are considered different when they consist of different edges.

输入:

Input consists of multiple test cases.
For each test case, the first line contains one integer N described as above.
N lines follows, each consists of N characters, either ’0′ or ’1′, representing the adjacency matrix of the graph.
The directed graph contains edge (i,j) if and only if the jth character of the ith line of the matrix is ’1′.
The graph consists of no more than 8 vertices.
End of input is indicated by a line consisting of a single 0.

输出:

Input consists of multiple test cases.
For each test case, the first line contains one integer N described as above.
N lines follows, each consists of N characters, either ’0′ or ’1′, representing the adjacency matrix of the graph.
The directed graph contains edge (i,j) if and only if the jth character of the ith line of the matrix is ’1′.
The graph consists of no more than 8 vertices.
End of input is indicated by a line consisting of a single 0.

样例输入:

2
00
00
2
01
10
0

样例输出:

0
2

题目大意:

给一个点数不超过8的无权有向图, 求树形图的数目.

 

简要分析:

根据点数很少这个条件, 我们自然想到搜索或者状态压缩动态规划, 而这两种做法都是正确的, 在这里我重点介绍第二种算法.

先枚举根, 再用f[mask1][mask2]表示mask1集合里的点已连通且mask2集合里的点皆是此树形图的叶子, 这样定义状态是因为只用一维状态对于不同的转移得到相同的树形图这种情况不是很好处理, 而二维状态就可以这样转移: 由mask1中的点向外连边扩展出点v, 那么v必为新的叶子, 此时我们强制v的标号大于mask2中点的标号时再转移, 这样就能做到既不重复也不遗漏地计算. 空间复杂度O(2^2n), 时间复杂度O(2^2n*n^2).

 

代码实现:

#include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const int MAX_N = 8, MAX_S = 1 << MAX_N;
 int n, m, t, dp[MAX_S][MAX_S];
 char g[MAX_N][MAX_N + 1];
 
 int main() {
     while (scanf("%d", &n) != EOF) {
         if (!n) break;
         for (int i = 0; i < n; i ++) {
             scanf("%s", g[i]);
             for (int j = 0; j < n; j ++) g[i][j] -= '0';
         }
 
         int upper = 1 << n, ans = 0;
         for (int i = 0; i < n; i ++) {
             memset(dp, 0, sizeof(dp));
             dp[1 << i][1 << i] = 1;
 
             for (int mask = 0; mask < upper; mask ++)
                 for (int s = mask; s; s = (s - 1) & mask)
                     for (int u = 0; u < n; u ++) if (mask & (1 << u))
                         for (int v = 0; v < n; v ++) if ((mask & (1 << v)) == 0 && g[u][v]) {
                             int m1 = mask | (1 << v);
                             int m2 = (s | (1 << v)) & (~(1 << u));
                             if (((1 << (v + 1)) - 1) >= m2) dp[m1][m2] += dp[mask][s];
                         }
 
             for (int s = 0; s < upper; s ++) ans += dp[upper - 1][s];
         }
 
         printf("%d\n", ans);
     }
     return 0;
 }


参考:http://www.cnblogs.com/zcwwzdjn/archive/2012/02/25/2367351.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  3. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.