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
西风萧瑟 阅读(2195)
评论(12) 编辑 收藏 引用 所属分类:
图论