首页 > 代码库 > 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(高斯消元)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。