URAL/1507

来自"NOCOW"

不说什么了，就是简单的矩阵乘法。。。

#include <iostream>
using namespace std;
int n,t,a[51][51],b[51][51]={0},c[51][51]={0},tmp[51][51]={0};
inline void mul(int a[51][51],int b[51][51])
{
    memset(tmp,0,sizeof(tmp));
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            for (int k=1;k<=n;++k)
                if (a[i][j]*b[j][k])
                    tmp[i][k]=1;
}
inline void power(int x)
{
    if (!x)
    {
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                c[i][j]=1;
        return;
    }
    else if (x == 1)
    {
        memcpy(c,a,sizeof(a));
        return;
    }
    power(x>>1);
    mul(c,c);
    memcpy(c,tmp,sizeof(tmp));
    if (x&1)  mul(a,c);
    memcpy(c,tmp,sizeof(tmp));
}
int main()
{
    cin >> n;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
        {
            cin >> t;
            if (t)  a[i][j]=1;
            else  a[i][j]=0;
        }
    power(n*(n-1));
    for (int i=n*(n-1);i<=n*(n+1);++i)
    {
        for (int j=1;j<=n;++j)
            for (int k=1;k<=n;++k)
                if (c[j][k])
                    b[j][k]=1;
        mul(a,c);
        memcpy(c,tmp,sizeof(tmp));
    }
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (!b[i][j])
            {
                cout << "No" << endl;
                return 0;
            }
    cout << "Yes" << endl;
    return 0;
}
//by zzy