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ǎ崽 閱讀(1099)
評論(2) 編輯 收藏 引用