解题思路

本题属于求线性方程组的稳态解，可通过迭代法（如高斯 - 赛德尔迭代）求解。关键点如下：

状态转移矩阵构建： 对于每个储罐 j，若其度数为 d j ​

，则其相邻储罐 i 将从 j 获得 X j t ​ /d j ​

的污染物量。 构建转移矩阵 P ，其中 P[i][j]=I ij ​ /d j ​

，表示从 j 到 i 的转移系数。若 j 的度数为 0，则 P[j][j]=1 ，其余为 0。 迭代收敛条件： 当相邻两次迭代的各储罐污染物量差异小于 10 −6

（或其他足够小的阈值）时，认为达到稳态。 迭代方法选择： 使用高斯 - 赛德尔迭代法，每次迭代利用最新计算的储罐值更新后续值，可加速收敛。 算法步骤： 输入处理：读取储罐数 N、管道数 M，初始污染物量，以及管道连接关系，构建邻接表和度数数组。 初始化转移矩阵：根据邻接表计算每个储罐的度数，并构建转移矩阵 P。 迭代求解： 初始化当前状态向量 X 为初始值。 每次迭代计算新状态向量 X_new，其中 X_new[i]=∑ j=1 N ​ P[i][j]⋅X[j] 。 计算 X_new 与 X 的绝对误差，若所有误差小于阈值（如 10 −8

），则终止迭代。 否则，将 X 更新为 X_new，继续迭代。 输出结果：将最终结果四舍五入到三位小数并输出，测试用例间用空行分隔。 #include #include #include #include using namespace std;

const double EPS = 1e-8; // 收敛阈值

int main() { int T; cin >> T; for (int t = 0; t < T; ++t) { int N, M; cin >> N >> M;

    vector<double> X(N); // 初始污染物量
    for (int i = 0; i < N; ++i) {
        cin >> X[i];
    }
    
    // 构建邻接表和度数数组
    vector<vector<int>> adj(N); // adj[j] 存储j的相邻节点（0-based）
    vector<int> degree(N, 0);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--; // 转为0-based
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }
    
    // 构建转移矩阵（隐式表示，通过邻接表计算）
    bool first_case = (t != 0);
    while (true) {
        vector<double> X_new(N, 0.0);
        bool converged = true;
        
        for (int j = 0; j < N; ++j) {
            double dj = degree[j];
            if (dj == 0) {
                X_new[j] = X[j]; // 度数为0时，状态不变
            } else {
                double val = X[j] / dj;
                for (int i : adj[j]) {
                    X_new[i] += val;
                }
            }
        }
        
        // 检查收敛性
        double max_diff = 0.0;
        for (int i = 0; i < N; ++i) {
            max_diff = max(max_diff, fabs(X_new[i] - X[i]));
        }
        if (max_diff < EPS) {
            break;
        }
        X = X_new;
    }
    
    // 输出结果
    if (first_case) {
        cout << endl; // 测试用例间空行
    }
    for (int i = 0; i < N; ++i) {
        cout << fixed << setprecision(3) << X[i] << endl;
    }
}
return 0;

}