http://acm.hdu.edu.cn/showproblem.php?pid=2807昨天比赛这道题目要求矩阵的乘法然后进行比较。。
算了一下复杂度是O(n^5)绝对超时。。
比赛的时候一直卡着，赛后才知道有一种好的算法--矩阵比较法
就是二维的矩阵乘以一个一维的矩阵使之降为一维，然后进行比较
这样的话就只用n^2的算法进行矩阵相乘了，复杂度降成了(n^4)顺利AC、。。。
#include<stdio.h>
#include<string>
struct H
{
int pos,time;
}q[100000];
struct Mat{
int matrix[80][80];
int yiwei[80];
}city[80];
bool map[80][80];
int m,n;
bool hash[80];
int bfs(int start,int end)
{
int i,head,tail;
head = tail = 0;
q[0].pos = start;
q[0].time = 0;
memset(hash,false,sizeof(hash));
while(head <= tail)
{
if(q[head].pos == end)
return q[head].time;
for(i=0;i<n;i++)
{
if(hash[i])
continue;
if(map[q[head].pos][i])
{
tail ++;
q[tail].pos = i;
q[tail].time = q[head].time + 1;
hash[i] = true;
}
}
head ++;
}
return -1;
}
bool judge(int x,int y)
{
int a[80],b[80];
int i,j,k;
for(i=0;i<n;i++)
{
if(i == x || i == y)
continue;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(j=0;j<m;j++) {
for(k=0;k<m;k++) {
a[j] += city[i].matrix[j][k] * (k+1);
}
}
for(j=0;j<m;j++) {
for(k=0;k<m;k++) {
b[j] += city[x].matrix[j][k] * a[k];
}
}
for(j=0;j<m;j++) {
if(b[j] != city[y].yiwei[j])
break;
}
if(j == m)
return true;
}
return false;
}
int main()
{
int i,j,k;
while(scanf("%d%d",&n,&m),n+m)
{
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
city[i].yiwei[j] = 0;
for(k=0;k<m;k++)
{
scanf("%d",&city[i].matrix[j][k]);
city[i].yiwei[j] += city[i].matrix[j][k] * (k+1);
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i == j)
map[i][j] = false;
else
map[i][j] = judge(i,j);
}
}
// for(i=0;i<n;i++)
// {
// for(j=0;j<n;j++)
// printf("%d ",map[i][j]);
// puts("");
// }
int x;
scanf("%d",&x);
while(x--)
{
int start,end,buf;
scanf("%d%d",&start,&end);
start --;
end --;
if(start >= n || end >= n)
{
puts("Sorry");
continue;
}
buf = bfs(start,end);
if(buf!=-1)
printf("%d\n",buf);
else
puts("Sorry");
}
}
return 0;
}posted on 2009-04-20 15:47
shǎ崽 阅读(1077)
评论(2) 编辑 收藏 引用