http://acm.hdu.edu.cn/showproblem.php?pid=2807

常规矩阵比较复杂度是O(n^2), 我们可把2维的数组乘以一个一维数组  来比较
通过这道题的测试,效果灰常让人吃惊。。。

常规比较的代码用C++提交超时,但是G++可以过掉,1484MS

#include <iostream>
using namespace std;
#define N 81
#define INF 99999999
int map[N][N], n, m;
struct node{
    
int Map[N][N];
} rec[N];

struct nnode{
    
int Map[N];
}recone[N];

void cmp(int a, int x)
{
    
int i;
    
for (i=1; i<=m; i++)        
        
if (recone[x].Map[i] != recone[0].Map[i])
            
return;
    map[a][x] 
= 1;
}

void creat(int a, int b)
{
    
int i, j, k, s;
    
for (i=1; i<=m; i++)
    {
        recone[
0].Map[i] = 0;
        
for (j=1; j<=m; j++)
        {
            recone[
0].Map[i] += rec[a].Map[i][j] * recone[b].Map[j];            
        }
    }
        
    
for (i=1; i<=n; i++)
        
if (i != a && i != b)
            cmp(a, i); 
//判断 a 与 i的关系
}

int main()
{
    
int i, j, k;
    
while (scanf("%d %d"&n, &m), n+m)
    {
        
for (i=1; i<=n; i++)
            
for (map[i][i]=0, j=i+1; j<=n; j++)
                map[i][j] 
= map[j][i] = INF; //初始化矩阵之间关系
            
            
for (k=1; k<=n; k++)
            {
                
for (i=1; i<=m; i++)
                {
                    recone[k].Map[i] 
= 0;
                    
for (j=1; j<=m; j++)
                    {
                        scanf(
"%d"&rec[k].Map[i][j]);
                        recone[k].Map[i] 
+= rec[k].Map[i][j] * j; //   2->1
                    }
                }
            } 
// 接受矩阵信息
            
            
for (i=1; i<=n; i++)
                
for (j=1; j<=n; j++)
                    
if (i != j)
                        creat(i, j); 
// 处理矩阵 i*j
                    
                    
for (k=1; k<=n; k++)
                        
for (i=1; i<=n; i++)
                            
for (j=1; j<=n; j++)
                                
if (map[i][k] + map[k][j] < map[i][j])
                                    map[i][j] 
= map[i][k] +map[k][j];
                                scanf(
"%d"&m);
                                
while (m--)
                                {
                                    scanf(
"%d %d"&i, &j);
                                    
if (map[i][j] != INF)
                                        printf(
"%d\n", map[i][j]);
                                    
else
                                        printf(
"Sorry\n");
                                }
    }
    
return 0;
}
posted on 2009-12-04 09:05 西风萧瑟 阅读(2154) 评论(12)  编辑 收藏 引用 所属分类: 图论

评论:
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-04 10:12 | oh no
恕我无知,G++是什么语言?  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-04 10:20 | 西风萧瑟
@oh no
g++是GNU的c++编译器而已 不是程序语言  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-04 10:31 | oh no
我知道是编译器,只是看到把它放在语言那栏下面
我就觉得奇怪,怎么把C++和G++来比较?
一个是语言,一个是编译器  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-04 11:21 | 西风萧瑟
@oh no
呵呵,理解上的误解吧,那个C++指的不是语言,而是Microsoft Visual C++编译器   回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path[未登录] 2009-12-07 08:15 | TimTopCoder
Microsoft Visual C++的编译器在用户不带任何参数的时候是比g++快的,实际上它本身编译的时候是带了很多参数的,特别是release模式,比debug在性能和大小上都高出了许多。。。。但g++也可以通过在编译时带各种优化参数达到。。只是记不下来那么多。。。  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-17 20:59 | akheyun
你的意思是判两个M*M的矩阵相等 只要判断他们分别乘同一个M*1的矩阵之后是否相等是吧?  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-17 21:10 | 西风萧瑟
@akheyun
一般情况下可以,概率问题。如果2个矩阵相等,那么转化成的1维矩阵一定相等。
否则,相等的概率很小很小  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-17 22:13 | akheyun
@西风萧瑟
存在两个不同的矩阵 同乘1个矩阵后相等啊。。概率不小啊 貌似随便都能列出些。。。
  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-17 22:16 | akheyun
@akheyun
例如1 2 * 1 3 1 * 1
2 4 2 2 4 2
结果都是 5
10  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-18 13:05 | 西风萧瑟
@akheyun
不好意思,你上面的例子是什么意思咯?
比较的是[n*m] 的矩阵 乘以 [m*1] 的矩阵所得到的[n*1]的矩阵  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path 2009-12-19 22:56 | akheyun
那个回复之后空格都缩回去了。。 其实是两个矩阵。。 我知道最后比较的是【n*1】的矩阵, 但是有很多情况下不同的[n*m]矩阵乘1个相同的[m*1]矩阵得到的[n*1]矩阵是相同的。。  回复  更多评论
  
# re: 矩阵的快速比较 HDU2807 The Shortest Path[未登录] 2009-12-21 22:14 | 西风萧瑟
@akheyun
对,但概率不是很大,除非你刻意的去找。对于[n*1]的矩阵,你可以用随机函数生成,这样更安全些。因为没那么多巧合咯~O(∩_∩)O~  回复  更多评论
  

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