hdu 4418 高斯消元解方程求期望

題意:

一個人在一條線段來回走(遇到線段端點就轉變方向)，現在他從起點出發，並有一個初始方向，

        每次都可以走1, 2, 3 ..... m步，都有對應著一個概率。問你他走到終點的概率

思路：

        方向問題很是問題，我們可以把線段改造成環，具體我們可以把除端點以外的點作為另一個半圓 和原來的線段拼成一個環，

方向就單一了，用dp[i]表示在i點的時候到達終點的期望步數，則dp[i]=dp[(i+1)%N]*p1+E[(i+2)%N]*p2+…E[(i+m)%N]*pm+1。

        這裡N為變成環以後的點數。注意到有些點是無法到達的，自然這些點的期望是無意義的，可以理解成正無窮，在實際列方程的         時候，我們不需要把這些點列入方程中去，這樣避免解方程的時候出現問題。所以我們可以先從起點進行bfs，將能到達的點             進行標號， 搜完後，有標號的點都是方程的未知數。然後對每個能到達的點列一個方程，高斯消元解出dp[起點]就是答案。

代碼：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 203;
const double  eps = 1e-9;
//高斯消元白書模板
//n ： 未知數個數，   a[][]為增廣矩陣
//把解放在    a[][n]中
bool gauss(double a[][maxn], int n) {
    int i, j, k, r;
    for (i = 0; i < n; i++) {
        r = i;
        for (j = i + 1; j < n; j++)
            if (fabs(a[j][i]) > fabs(a[r][i]))
                r = j;

        if (fabs(a[r][i]) < eps)
            return 0;

        if (r != i)
            for (j = 0; j <= n; j++)
                swap(a[r][j], a[i][j]);


		//根據精度需要選擇以下其一：
        //低精度
        for (k = i + 1; k < n; k++) {
            r = a[k][i] / a[i][j];
            for (j = i; j <= n; j++)
                a[k][j] -= r * a[i][j];
        }
        //

        //高精度
        for (j = n; j >= i; j--)
            for (k = i + 1; k < n; k++)
                a[k][j] -= a[k][i] / a[i][i] * a[i][j];
        //
    }

	//回代過程
    for (i = n - 1; i >= 0; i--) {
        for (j = i + 1; j < n; j++)
            a[i][n] -= a[j][n] * a[i][j];
        a[i][n] /= a[i][i];
    }
    return 1;
}
int n, m, t, s, d, N;
double p[103];
int idx[maxn], id;   //idx給能到達的點標號，id為能到達的點的個數，也是方程未知數的個數
void bfs(int s) {
    id = 0;
    memset(idx, -1, sizeof(idx));
    queue<int> q;
    q.push(s);
    idx[s] = id++;
    int i;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (i = 1; i <= m; i++) {
            if (fabs(p[i]) < eps)
                continue;
            int v = (u + i) % N;
            if (idx[v] == -1) {
                idx[v] = id++;
                q.push(v);
            }
        }
    }
}
double a[maxn][maxn];
//s起點  t終點
int main() {
    int i, j, cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d%d%d%d", &n, &m, &t, &s, &d);
        for (i = 1; i <= m; i++) {
            scanf("%lf", &p[i]);
            p[i] /= 100;
        }
        if(s == t) {    //必須特判
            printf("0.00\n");
            continue;
        }
        N = (n - 1) << 1;
        if (d == 1) s = N - s;

        bfs(s);
        if (idx[t] == -1 && idx[N-t] == -1) {
            printf("Impossible !\n");
            continue;
        }
		//id變成了方程組未知數的個數
        memset(a, 0, sizeof(a));
        for(i = 0; i < N; i++)
            if(~idx[i]) {
                a[idx[i]][idx[i]] = 1;
                if(i == t || i == N-t)
                    continue;
                for(j = 1; j <= m; j++) {
                    int v = (i+j)%N;
                    if(idx[v] != -1) {
                        a[idx[i]][idx[v]] -= p[j];
                        a[idx[i]][id] += j*p[j];
                    }
                }
            }
        if(gauss(a, id)) printf("%.2f\n", a[idx[s]][id]);
        else printf("Impossible !\n");
    }
    return 0;
}