Comparing answers

离散数学真的要好好学啊:一个邻接矩阵(这个矩阵一定是n×n的方阵,n是图的节点个数),表示的是从i到j有几条通路的时候,矩阵的1次方就代表从从i到j长度为1的路径通路的个数,矩阵的2次方就代表从从i到j长度为2的路径通路的个数...矩阵的n次方就代表从从i到j长度为n的路径通路的个数

【题目链接】Comparing answers

【题目类型】数学矩阵

&题解：

这题就是求矩阵的平方是否等于所给的矩阵,但是要用n^{2的算法来解,n}3算法肯定是不行的.

我们可以另找一个向量C 如果A* A=B 那么(A* A)* C=B* C 又有矩阵乘法满足结合律,所以A* (A* C)=B* C 又因为C只有n行1列,所以可以用n^2算法求出上面的式子,如果他们不相等,那就是NO,反之.

【时间复杂度】\(O(n^2)\)

&代码：

#include <cstdio>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

using ll=long long;

const int maxn= 1e3 +9;

typedef vector<ll> vec;

typedef vector<vec> mat;

ll n,M=1e9;

vec mul(mat &A,vec &B)

{

	vec C(A.size());

	for(int i=0;i<A.size();i++)

	for(int j=0;j<B.size();j++){

		C[i]=(C[i]+A[i][j]*B[j]);

	}

	return C;

}

int main()

{

	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	freopen("E:1.txt","r",stdin);

	while(cin>>n){

		if(n==0)break;

		mat A(n,vec(n)),B(n,vec(n));

		for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

			cin>>A[i][j];

		for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

			cin>>B[i][j];

		vec H(n),TE(n);

		for(int i=0;i<n;i++){

			H[i]=i+1;

			TE[i]=i+1;

		}

		H=mul(A,H);

		H=mul(A,H);

		TE=mul(B,TE);

		int f=1;

		for(int i=0;i<n;i++){

			if(TE[i]!=H[i])

				f=0;

		}

		if(f)

			cout<<"YES"<<endl;

		else

			cout<<"NO"<<endl;

	}

	return 0;

}

巴特西

CSU 1849 Comparing answers(数学矩阵)

Comparing answers

最新文章

热门文章