[Solution][Aho-Corasick Auto Machine][Gauss]JSOI2009 有趣的游戏

【题目】

戳这里

【思路】

构建Trie图,然后枚举转移构建方程组进行高斯消元。注意如果一个节点是串的尾节点就不用向下转移了。

显然到达一个点的概率是到达所有能够到达这个点的点的概率与到达这个点的转移发生概率的乘积和。

各种注意精度!!

输出答案时要判断结果是否在内,不在的话直接输出.

【代码】

/**************************************************************
    Problem: 1444
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:8 ms
    Memory:924 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline double _abs(double x)
{
    return x < 0 ? -x : x;
}
inline void _swap(double &x , double &y)
{
    double change = x;
    x = y;
    y = change;
}
double p[10] , muply;
int ch[101][10] , f[101] , val[101] , ind , get[11];
double A[102][102];
int main()
{
    int n , L , m;
    scanf("%d%d%d" , &n , &L , &m);
    int a , b;
    register int i , j , k , l;
    for(i = 0 ; i < m ; ++i)
    {
        scanf("%d%d" , &a , &b);
        p[i] = a / double(b);
    }
    int tmp , ins;
    char s[11];
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%s" , s);
        tmp = 0;
        for(j = 0 ; j < L ; ++j)
        {
            ins = s[j] - 'A';
            if (!ch[tmp][ins])
                ch[tmp][ins] = ++ind;
            tmp = ch[tmp][ins];
        }
        get[i] = tmp;
        val[tmp] = i;
    }
    queue<int> q;
    for(i = 0 ; i < m ; ++i)
        if (ch[0][i])
            q.push(ch[0][i]);
    int r , u , v;
    while(!q.empty())
    {
        r = q.front();
        q.pop();
        for(i = 0 ; i < m ; ++i)
        {
            u = ch[r][i];
            if (!u)
            {
                ch[r][i] = ch[f[r]][i];
                continue;
            }
            q.push(u);
            v = f[r];
            while(v && !ch[v][i])
                v = f[v];
            f[u] = ch[v][i];
        }
    }
    for(i = 0 ; i <= ind ; ++i)
    {
        A[i][i] = -1;
        if (val[i])
            continue;
        for(j = 0 ; j < m ; ++j)
            A[ch[i][j]][i] += p[j];
    }
    for(i = 0 ; i <= ind ; ++i)
        A[0][i] = val[i] ? 1 : 0;
    A[0][ind + 1] = 1;
    for(i = 0 ; i <= ind ; ++i)
    {
        k = i;
        for(j = i + 1 ; j <= ind ; ++j)
            if (_abs(A[k][i]) < _abs(A[j][i]))
                k = j;
        if (k != i)
            for(j = i ; j <= ind + 1 ; ++j)
                _swap(A[i][j] , A[k][j]);
        for(j = i + 1 ; j <= ind ; ++j)
        {
            if (_abs(A[i][i]) > 1e-6)
            {
                muply = -A[j][i] / A[i][i];
                A[j][i] = 0;
                for(k = i + 1 ; k <= ind + 1 ; ++k)
                    A[j][k] += muply * A[i][k];
            }
        }
    }
    for(i = ind ; i >= 0 ; --i)
    {
        for(j = i + 1 ; j <= ind ; ++j)
            A[i][ind + 1] -= A[i][j] * A[j][ind + 1];
        A[i][ind + 1] /= A[i][i];
    }
    for(i = 1 ; i <= n ; ++i)
    {
        if (A[get[i]][ind + 1] > 0 && A[get[i]][ind + 1] <= 1)
            printf("%.2f\n" , A[get[i]][ind + 1]);
        else
            puts("0.00");
    }
    return 0;
}
comments powered by Disqus