HDU 2807 The Shortest Path(矩阵比较+Floyd)
http://acm.hdu.edu.cn/showproblem.php?pid=2807
题意:有N个城市,每个城市用一个M*M的矩阵表示.如果矩阵A*矩阵B== 矩阵C,那么我们说城市A到城市C有一条长度为1的路.现在你要回答对于特定的两个城市是否存在路,如果存在的话,最短路是多少?
分析:
本题可以直接暴力枚举任意两个城市a和b然后看他们相乘的结果是否和N个矩阵里面的c矩阵相等.如果相等,那么a->c有长为1的路.注意:这里a与b与c要互不相同.
a与b不同是题目要求的,a与c也要不同.因为如果a和c是同一个城市,那么a有一条到自己的长度为1的边,明显不对.
网上也有很多用矩阵乘法优化之后来做比较的.具体思路是:
“如果A*B=C,则A*B*D=C*D,D为m*1的矩阵。设d=B*D,则A*B*D=A*d;同样设dd=A*d,cc=C*D;最后比较dd是否等cc就行了。”
这里我有个疑问,上面的证明只能推出A*B=C -> dd=cc.
但是dd=cc能推出A*B=C吗?
不一定吧? 因为D矩阵是m*1阶的,都不存在逆矩阵.
AC代码: 暴力解决.250ms,与上面的优化相比也没慢多少.不过注意我代码中矩阵相乘的实现方式.
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=80+5;
int n,m;
struct Matrix
{
int v[maxn][maxn];
Matrix(){ memset(v,0,sizeof(v)); }
void read(int m)
{
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
scanf("%d",&v[i][j]);
}
Matrix operator*(Matrix &B)const
{
Matrix C;
for(int i=0;i<m;i++)
for(int k=0;k<m;k++)if(v[i][k])//若按正常的i,j,k顺序循环,则会变成1700ms
for(int j=0;j<m;j++)if(B.v[k][j])
C.v[i][j] += v[i][k]*B.v[k][j];
return C;
}
bool operator == (Matrix &B)const
{
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
if(v[i][j]!=B.v[i][j]) return false;
return true;
}
}ma[maxn];
int d[maxn][maxn];
int main()
{
while(scanf("%d%d",&n,&m)==2&&n)
{
for(int i=0;i<n;i++)
ma[i].read(m);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]= i==j?0:INF;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)if(i!=j)
{
Matrix res = ma[i]*ma[j];
for(int k=0;k<n;k++)if(i!=k&&j!=k)
if(res == ma[k])
d[i][k]=1;
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(d[i][k]<INF && d[k][j]<INF)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
int k;
scanf("%d",&k);
while(k--)
{
int u,v;
scanf("%d%d",&u,&v);
u--,v--;
if(d[u][v]==INF) printf("Sorry\n");
else printf("%d\n",d[u][v]);
}
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
ACM题库,一些题目和答案,以及解题报告,传上来共享
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
杭电OnlineJudge 200-2099的解题报告
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区,才知道这题有如下问题: speed...
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧