首页 > 代码库 > UVA 10828 Back to Kernighan-Ritchie(高斯消元)

UVA 10828 Back to Kernighan-Ritchie(高斯消元)

高斯消元求概率

对于非起点,期望x[i] = ∑x[j] / deg[j]

 

#include<cstdio>#include<iostream>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>#include<map>#include<queue>#include<vector>#include<cmath>#include<utility>using namespace std;typedef long long LL;const int N = 108, INF = 0x3F3F3F3F;const double eps = 1e-8;double f[N][N];std::vector<int> g[N];bool inf[N];template<typename T>void gauss(T A[N][N], int n){    for(int i = 0; i < n; i++){        int r = i;        for(int j = i + 1; j < n; j++){            if(abs(A[j][i]) > abs(A[r][i])){                r = j;            }        }        if(abs(A[r][i]) < eps){            continue;        }        if(r != i){            for(int j = 0; j <= n; j++){                swap(A[r][j], A[i][j]);            }        }        for(int k = 0; k < n; k++){            if(k != i){                for(int j = n; j >= i; j--){                    A[k][j] -=  A[k][i] / A[i][i] * A[i][j];                }            }        }    }}int main(){    int cas = 0, n, q;    while(~scanf("%d", &n) && n){        for(int i = 0; i <= n; i++){            g[i].clear();        }        int u, v;        while(scanf("%d %d", &u, &v) &&  u && v){            u--;            v--;            g[u].push_back(v);        }        memset(f, 0, sizeof(f));        for(int i = 0; i < n; i++){            f[i][i] = -1;            for(int j = 0; j < g[i].size(); j++){                f[g[i][j]][i] += 1.0 / (double)g[i].size();            }        }        f[0][n] = -1;        gauss(f, n);        memset(inf, 0, sizeof(inf));        for(int i = n - 1; i >= 0; i--){            if(abs(f[i][i]) < eps && abs(f[i][n]) > eps){                inf[i] = 1;            }            for(int j = i + 1; j < n; j++){                if(inf[j] && abs(f[i][j]) > eps){                    inf[i] = 1;                    break;                }            }        }        printf("Case #%d:\n", ++cas);        scanf("%d", &q);        while(q--){            int u;            scanf("%d", &u);            u--;            if(inf[u]){                printf("infinity\n");            }else{                printf("%.3f\n", (abs(f[u][u]) < eps )? 0.0 : abs(f[u][n] / f[u][u]));            }        }    }    return 0;}

  

UVA 10828 Back to Kernighan-Ritchie(高斯消元)