2 条题解
-
1
搬运工 (syrth0p1) LV 10 @ 2026-03-13 23:31:26
#include <iostream> #include <vector> #include <cmath> #include <cstdio> using namespace std; const int MAX_K = 10005; vector<pair<int, int>> neighbors[MAX_K]; double b_orig[MAX_K]; double x[MAX_K], r[MAX_K], p_vec[MAX_K], Ap[MAX_K]; int main() { int N, M; scanf("%d %d", &N, &M); int K = N * M; // 处理p数组:N-1行,每行M个整数(上下边) for (int i = 0; i < N-1; ++i) { for (int j = 0; j < M; ++j) { int w; scanf("%d", &w); int id1 = i * M + j; int id2 = (i+1) * M + j; neighbors[id1].emplace_back(id2, w); neighbors[id2].emplace_back(id1, w); b_orig[id1] += w; b_orig[id2] += w; } } // 处理q数组:N行,每行M-1个整数(左右边) for (int i = 0; i < N; ++i) { for (int j = 0; j < M-1; ++j) { int w; scanf("%d", &w); int id1 = i * M + j; int id2 = i * M + (j+1); neighbors[id1].emplace_back(id2, w); neighbors[id2].emplace_back(id1, w); b_orig[id1] += w; b_orig[id2] += w; } } int Q; scanf("%d", &Q); const double eps = 1e-10; while (Q--) { int u, v, s, t; scanf("%d %d %d %d", &u, &v, &s, &t); int S = u * M + v; int T = s * M + t; if (S == T) { printf("0\n"); continue; } // 初始化x, r, p_vec for (int id = 0; id < K; ++id) { x[id] = 0.0; r[id] = (id == T) ? 0.0 : b_orig[id]; p_vec[id] = r[id]; } double old_rr = 0.0; for (int id = 0; id < K; ++id) { old_rr += r[id] * r[id]; } int max_iter = K; for (int iter = 0; iter < max_iter; ++iter) { // 计算Ap = A * p_vec Ap[T] = p_vec[T]; for (int id = 0; id < K; ++id) { if (id == T) continue; double val = neighbors[id].size() * p_vec[id]; for (auto &edge : neighbors[id]) { int neigh = edge.first; if (neigh != T) val -= p_vec[neigh]; } Ap[id] = val; } // 计算p_Ap double p_Ap = 0.0; for (int id = 0; id < K; ++id) { p_Ap += p_vec[id] * Ap[id]; } if (fabs(p_Ap) < eps) break; double alpha = old_rr / p_Ap; // 更新x和r for (int id = 0; id < K; ++id) { x[id] += alpha * p_vec[id]; r[id] -= alpha * Ap[id]; } // 计算new_rr double new_rr = 0.0; for (int id = 0; id < K; ++id) { new_rr += r[id] * r[id]; } if (sqrt(new_rr) < eps) break; double beta = new_rr / old_rr; // 更新p_vec for (int id = 0; id < K; ++id) { p_vec[id] = r[id] + beta * p_vec[id]; } old_rr = new_rr; } printf("%d\n", (int)x[S]); } return 0; } -
-21@ 2016-01-10 18:27:57
虽然我没有AC但我来抢个沙发
- 1