Cho ma trận kề của đồ thị có hướng G. Lặp lại cho đến khi đồ thị rỗng: chọn một đỉnh, xóa đỉnh đó và tất cả đỉnh có thể đạt được từ nó (theo các cạnh). Hãy tìm số kỳ vọng các lần thực hiện phép toán.
Ví dụ
Với ma trận kề 3x3 (hình ảnh), đầu ra là 1.6667. Giải thích: chọn A xóa hết (1 phép), chọn B xóa B,C rồi chọn A (2 phép), chọn C tương tự. Kỳ vọng = (1+2+2)/3 = 1.6667.
Giải thuật
Tính bao truyền thông (transitive closure) bằng Floyd-Warshall. Với mỗi đỉnh i, đếm số đỉnh k có đường đi đến i (tức G[j][i] = 1). Kỳ vọng là tổng 1/k cho mọi đỉnh.
Mã C++
#include <bits/stdc++.h>
using namespace std;
double solve(vector<vector<int>> G) {
int n = G.size();
for (int i = 0; i < n; ++i) G[i][i] = 1;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (G[i][k] && G[k][j])
G[i][j] = 1;
double ans = 0;
for (int i = 0; i < n; ++i) {
int k = 0;
for (int j = 0; j < n; ++j)
if (G[j][i]) ++k;
ans += 1.0 / k;
}
return ans;
}
int main() {
vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } };
cout << solve(G) << endl;
}
Đầu vào / Đầu ra
Input: { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }
Output: 1.66667