vector<int> mine (n, INF), sele (n, -1); что значит?
- User
vector min_e (n, INF), sel_e (n, -1); что значит?
- Assistant
В данном контексте, "vector min_e (n, INF)" означает, что создается вектор "min_e" размерности "n" и заполняется элементами со значением "INF". Здесь "INF" представляет собой какое-либо большое значение, которое обычно используется для обозначения отсутствия ребра или бесконечности.
А "vector sel_e (n, -1)" означает, что создается вектор "sel_e" размерности "n" и заполняется элементами со значением "-1". В данном случае, "-1" может быть использовано для обозначения отсутствия выбранного ребра или некоторого неопределенного значения.
- User
// входные данные int n; vector < vector > g; const int INF = 1000000000; // значение "бесконечность"
// алгоритм vector used (n); vector min_e (n, INF), sel_e (n, -1); min_e[0] = 0; for (int i=0; i<n; ++i) { int v = -1; for (int j=0; j<n; ++j) if (!used[j] && (v == -1 || min_e[j] < min_e[v])) v = j; if (min_e[v] == INF) { cout << "No MST!"; exit(0); }
used[v] = true; if (sel_e[v] != -1) cout << v << " " << sel_e[v] << endl; for (int to=0; to<n; ++to) if (g[v][to] < min_e[to]) { min_e[to] = g[v][to]; sel_e[to] = v; }} Перепеши на питоне
- Assistant
n = int(input()) g = [] INF = 1000000000
used = [False] * n min_e = [INF] * n sel_e = [-1] * n min_e[0] = 0
for i in range(n): v = -1 for j in range(n): if not used[j] and (v == -1 or min_e[j] < min_e[v]): v = j if min_e[v] == INF: print("No MST!") exit(0)
used[v] = True if sel_e[v] != -1: print(v, sel_e[v]) for to in range(n): if g[v][to] < min_e[to]: min_e[to] = g[v][to] sel_e[to] = v