cf 236 div2 E Strictly Positive Matrix 矩阵阶乘和图上路径计数（可达）有关问题

cf 236 div2 E Strictly Positive Matrix 矩阵阶乘和图上路径计数（可达）问题

官方题解：

402E - Strictly Positive Matrix / 403C - Strictly Positive Matrix

Let's look at the matrix a as a connectivity matrix of some graph with n vertices. Moreover, if aij > 0, then we have directed edge in the graph between nodes (i, j). Otherwise, if aij = 0 that graph does not contains directed edge between pair of nodes (i, j). Let b = ak. What does bij means? bij is the number of paths of length exactly k in our graph from vertex i to vertex j. Let pos is an integer, such thata[pos][pos] > 0. That is, we have a loop in the graph. So, if from the vertex pos achievable all other vertexes and vice versa, from all other vertices reachable vertex pos, then the answer is YES, otherwise the answer is NO. If reachability is missing, it is clear that for anyk akipos = 0. If reachability there, we will be able to reach self-loop, use self-loop "to twist", and after that we will go to some another vertex.

大概题意:给定一个矩阵A（n*n的），对角线为1，其它位置为0或1.B= A^k，问是否存在某个k使得B中每个元素都为1.

矩阵阶乘和图上路径计数问题的转换：

（矩阵的元素为A[i][j] = 1代表图上点i可达点j，特殊的A[i][i] = 1。表示点i存在自环。）

转化为图的问题。对应的图为:

n个点，A[i][j] = 1,则i和j之间连边，否者不连。

则B = A^k，B[i][j]代表的含义为，从i到j的路径长度为k的路径的个数。

由于本题中对角线为1，即任意点存在子环，则如果存在从i到j的长度为k 的路径，则存在从i到j长度为k+1，k+2.。。的路径。

所以只需判断可到达即可，即任一点可到达其他所有点。可用floyd，判强连通为1，或判任意点都和同一点在一个环上即可（必要条件）。

本题是判断是否存在，则用必要条件去判断即可

floyd的解法和判任意点都和同一点在一个环上的解法：

int n;
bitset<2010>f[2010];
int main ()
{
    RI(n);
    REP(i, n) REP(j, n)
    {
        int x;
        RI(x);
        f[i][j] = !!x;
    }
    REP(k, n) REP(i, n)
    if (f[i][k]) f[i] |= f[k];
    int fla = 1;
    REP(i, n) REP(j, n) if (!f[i][j])
    {
        fla = 0; break;
    }
    if (fla) puts("YES");
    else puts("NO");
    return 0;
}

int n;
bool f[2010][2010];
bool used[2010], rused[2010];
void dfs(int u)
{
    used[u] = 1;
    REP(i, n) if (f[u][i] && !used[i]) dfs(i);
}
void rdfs(int u)
{
    rused[u] = 1;
    REP(i, n) if (f[i][u] && !rused[i]) rdfs(i);
}
int main ()
{
    RI(n);
    REP(i, n) REP(j, n)
    {
        int x;
        RI(x);
        f[i][j] = !!x;
    }

    dfs(0);
    rdfs(0);
    int fla = 1;
    REP(i, n) if (!used[i] || !rused[i])///都为1说明成环
        fla = 0; break;

    if (fla) puts("YES");
    else puts("NO");
    return 0;
}

下题是图上路径计数问题转化成矩阵阶乘问题：

ac自动机中求长度为L的特定字符串的个数， AC自动机 其实 就是创建了一个状态的转移图（也是一个图），思想很重要

详见:http://www.cnblogs.com/kuangbin/p/3164106.html

中的

POJ 2778 DNA Sequence

HDU 2243 考研路茫茫——单词情结