Savage
13-12-2002, 00:50
give the system of two-way roads.Determine if it is possible, after building three additional new roads, from the chosen city to reach each of the remaining cities, travelling distance not more than T units( unit = a road directly from one city to the other )
mình dùng bool adjacency matrix representation A ( a[i,j] = {0,1} )
nếu a[i,j]=1 thì có nghĩa là từ thành phố i tới thành phố j tồn tại một đừong đi trực tiếp- distance=1 unit - ( không quan tâm đến trọng số nhé ).
bây giờ ta bình phương A lên ( lưu ý đay là matrix bool ) , kếu quả nếu a(n)[i,j] = 1 thì suy ra tồn tại một đường đi có độ dài max = 2 unit từ i tới j ...( cái này chứng minh được ) , and so fourth ta làm tương tự đến khi có Matrix A mũ T thì suy ra nếu a(T)[i,j]=1 thì tồn tại ít nhất một đừong đi có độ dài T từ i tới j....
bây giờ tình matrix D = tổng của các A(n) trong đó n chạy từ 1 tới T - A(n) nghĩa là matrix mũ n của A
như vậy nếu bây giờ D[I,j] = 1 thì có nghĩa là sẽ tồn tại một đường đi có độ dài lớn nhất là T từ I tới j
-OK ! đó là lý thuyết nhé , còn bài này thì sao ???
bây giờ ta tính D của bài này , sau đó xem xét phần tử nào mà = 0 thì sẽ là cái ta quan tâm . ta sẽ phải làm thế nào để tất cả các số 0 này trở thành số 1 ???
đến đây thì lại là vấn đề của Algebra rồi , các đại ca thử suy nghĩ xem làm thế nào mà chỉ cần thêm 3 cái a[I,j] =1 ta nhận đựợc tất cả D bằng 1 hết… ( tất nhiên khẳ năng có thể là không có nghiệm nào , nhưng đây ta giả sử là có nghiệm ..) thì thuật toán tiếp theo thế nào nhỉ các đại ca Algebra ??
Có bác nào có thuật toán mà không dùng đến cái bool adjacency matrix thì post lên nhé !
mình dùng bool adjacency matrix representation A ( a[i,j] = {0,1} )
nếu a[i,j]=1 thì có nghĩa là từ thành phố i tới thành phố j tồn tại một đừong đi trực tiếp- distance=1 unit - ( không quan tâm đến trọng số nhé ).
bây giờ ta bình phương A lên ( lưu ý đay là matrix bool ) , kếu quả nếu a(n)[i,j] = 1 thì suy ra tồn tại một đường đi có độ dài max = 2 unit từ i tới j ...( cái này chứng minh được ) , and so fourth ta làm tương tự đến khi có Matrix A mũ T thì suy ra nếu a(T)[i,j]=1 thì tồn tại ít nhất một đừong đi có độ dài T từ i tới j....
bây giờ tình matrix D = tổng của các A(n) trong đó n chạy từ 1 tới T - A(n) nghĩa là matrix mũ n của A
như vậy nếu bây giờ D[I,j] = 1 thì có nghĩa là sẽ tồn tại một đường đi có độ dài lớn nhất là T từ I tới j
-OK ! đó là lý thuyết nhé , còn bài này thì sao ???
bây giờ ta tính D của bài này , sau đó xem xét phần tử nào mà = 0 thì sẽ là cái ta quan tâm . ta sẽ phải làm thế nào để tất cả các số 0 này trở thành số 1 ???
đến đây thì lại là vấn đề của Algebra rồi , các đại ca thử suy nghĩ xem làm thế nào mà chỉ cần thêm 3 cái a[I,j] =1 ta nhận đựợc tất cả D bằng 1 hết… ( tất nhiên khẳ năng có thể là không có nghiệm nào , nhưng đây ta giả sử là có nghiệm ..) thì thuật toán tiếp theo thế nào nhỉ các đại ca Algebra ??
Có bác nào có thuật toán mà không dùng đến cái bool adjacency matrix thì post lên nhé !