Re: [问题] 30 ITSA-Problem2.图形简单性质

楼主: ACMANIAC (請肥宅救救肥宅)   2014-05-05 18:03:56
最简单的方法,用 Floyd-Warshall 算法
原本题目给的 adjacency matrix...
权重要先改一下,相连的边长是 1,未相连的是 infinity
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
}
时间复杂度 O(n^3)
※ 引述《goodwayhow 看板: C_and_CPP》之铭言:
: 开发平台(Platform): (Ex: VC++, GCC, Linux,
: C++
: 问题(Question):
: 想请问这题关于无向图diameter判断多大,会不会有任两顶点都不会相连?
: http://140.116.249.152/e-Tutor/mod/programming/view.php?id=19474
: 喂入的资料(Input):
: 3
: 0 1 1
: 1 0 1
: 1 1 0
: 预期的正确结果(Expected Output):
: 3 3 2 1
: 错误结果(Wrong Output):
: 这提是放在etuto上题目,所以不清楚背后测资怎样,但自行判断输出都没问题
: 程式码(Code):(请善用置底文网页, 记得排版)
: 这是我diameter的想法,不知版大有无更好的方法建议小弟
: for(int i=0;i<n;i++)
: {
: for(int j=0;j<n;j++)
: {
: if(i!=j)
: {
: if(a[i][j]==0)
: { //先找到不相连的座标
: temp1[s1++]=j;//纪录y座标j
: temp2=temp1[0];
: for(int k=0;k<n;k++)
: {
: if(a[temp2][k]==1)//然后把y座标放到x,从x
: 那一列开始找到相连点
: {
: diam++;
: temp2=k;
: break;
: }
: if(diam==n-1)
: {
: break;
: }
: }
: }
: }
: }
: }
: 补充说明(Supplement):
作者: goodwayhow   2014-05-05 18:12:00
感谢大大!!!

Links booklink

Contact Us: admin [ a t ] ucptt.com