随笔-72  评论-126  文章-0  trackbacks-0
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ǎ崽 阅读(1044) 评论(2)  编辑 收藏 引用

评论:
# re: 又学了一招,矩阵的比较 2009-05-02 21:18 | dragon123
您这样做是不对的吧

1*2矩阵 (1000,2) 和(996,4)
1000*1+2*2==996*1+4*2 但是它们不是相同的吧?
  回复  更多评论
  
# re: 又学了一招,矩阵的比较 2009-05-06 18:42 | shǎ崽
这个有一定概率性的
不过出现这样的几率非常小

也可以随机出数据
for(int i = 0; i < n; i ++)
ku[i] = rand()%10000;

然后用数组ku作为一维数组去进行降维  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理