Graph Automata Player

时间：2014-07-27 11:47:03 收藏：0 阅读：233

题意：
给n个点的有向图，边以邻接矩阵形式给出，如果为1则有边，为0无边。然后给出0时刻每个点的一个值，为0或1，输入一个T，输出-T时刻每个点的值：确定的话就输出，不确定的话按照题目要求输出error信息
题目背景：t时刻，每个点有一个值，那么t+1时刻，如果一个点发出的边的终点值为一的个数为奇数个，那么t+1时刻这个点的值就是1；否则为0
分析：
奇数边为零，偶数边为一，异或就可以实现。假设t时刻每个点的值的向量为x，那么x乘以邻接矩阵（加法改成异或操作）得到的向量就是t+1时刻的每个点的值。那么，其实就是邻接矩阵 * 邻接矩阵 * …… * 邻接矩阵 * goal = now（goal是要求的时间的值的列向量，now是当前的值的列向量）。快速幂解决邻接矩阵的T次幂，然后高斯消元即可。
思考：
其实高斯消元可以解决的问题，就是将矩阵求逆矩阵乘以等式右边，但是逆矩阵可能不存在。所以，可以用逆矩阵求解的都应该考虑到高斯消元，并且高斯消元还可以求逆矩阵不存在的情况（无解，多解）。

const int maxn = 310;

struct Mat
{
    int n, m;
    bool v[maxn][maxn];
    Mat (int n = 0, int m = 0, int zero = 0)
    {
        this->n = n;
        this->m = m;
        if (zero)
            REP(i, n) REP(j, m)
                v[i][j] = false;
    }
} ipt, now;

Mat mul(Mat& a, Mat& b)
{
    Mat ret(a.n, b.m, true);
    REP(i, a.n) REP(k, b.m) REP(j, a.m)
    {
        ret.v[i][k] ^= (a.v[i][j] & b.v[j][k]);
    }
    return ret;
}

Mat qpow(Mat& a, int b)
{
    Mat ret(a.n, a.n);
    int cnt = 0;
    while (b)
    {
        if (b & 1)
        {
            if (cnt == 0)
            {
                cnt = 1;
                ret = a;
            }
            else
                ret = mul(ret, a);
        }
        b >>= 1;
        a = mul(a, a);
    }
    return ret;
}

bool a[maxn][maxn];
int gauss(int N, int M)
{
    int r, c, pvt;
    bool flag;
    for (r = 0, c = 0; r < N && c < M; r++, c++)
    {
        flag = false;
        for (int i = r; i < N; i++)
            if (a[i][c])
            {
                flag = a[pvt = i][c];
                break;
            }
        if (!flag)
        {
            r--;
            continue;
        }
        if (pvt != r)
            for (int j = r; j <= M; j++)
                swap(a[r][j], a[pvt][j]);
        for (int i = r + 1; i < N; ++i) {
            if (a[i][c])
            {
                a[i][c] = false;
                for (int j = c + 1; j <= M; ++j)
                    if (a[r][j])
                        a[i][j] = !a[i][j];
            }
        }
    }
    for (int i = r; i < N; i++)
        if (a[i][M])
            return -1;
    if (r < M)
        return M - r;
    for (int i = M - 1; i >= 0; i--)
    {
        for (int j = i + 1; j < M; j++)
            if (a[i][j])
                a[i][M] ^= a[j][M];
        a[i][M] /= a[i][i];
    }
    return 0;
}

int main()
{
    int n, T;
    while (~RI(n))
    {
        ipt.n = ipt.m = now.m = n;
        now.n = 1;
        REP(i, n) REP(j, n)
            RI(ipt.v[i][j]);
        REP(i, n)
            RI(a[i][n]);
        RI(T);
        ipt = qpow(ipt, T);
        REP(i, n) REP(j, n)
                a[i][j] = ipt.v[i][j];
        int ret = gauss(n, n);
        if (ret == 0)
            REP(i, n)
                printf("%d%c", a[i][n], (i == n - 1 ? '\n' : ' '));
        else if (ret > 0)
            puts("ambiguous");
        else
            puts("none");
    }
    return 0;
}

原文：http://blog.csdn.net/wty__/article/details/38148593