题解

2 条题解

  • 1
    @ 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

信息

ID
1872
难度
8
分类
线性代数 | 概率论 | 其他 点击显示
标签
递交数
51
已通过
6
通过率
12%
被复制
5
上传者