首页 > 代码库 > UVA-10828 (概率期望+高斯消元)
UVA-10828 (概率期望+高斯消元)
题意：
给个有向图,每个节点等概率转移到它的后继节点,现在问一些节点的期望访问次数;
思路：
对于一个点v,Ev=Ea/d[a]+Eb/d[b]+Ec/d[c];a,b,c是v的前驱节点;
然后按这个列出方程,进行高斯约旦消元,然后判断是否可达和是否为0;
代码是白书上的;
AC代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <bits/stdc++.h>#include <stack>#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)#define mst(ss,b) memset(ss,b,sizeof(ss));#define ll long long;typedef long long LL; template<class T> void read(T&num) { char CH; bool F=false; for(CH=getchar();CH<‘0‘||CH>‘9‘;F= CH==‘-‘,CH=getchar()); for(num=0;CH>=‘0‘&&CH<=‘9‘;num=num*10+CH-‘0‘,CH=getchar()); F && (num=-num);}int stk[70], tp;template<class T> inline void print(T p) { if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + ‘0‘); putchar(‘\n‘);} const LL mod=1e9+7;const double PI=acos(-1.0);const LL inf=1e18;const int N=1e6+2000;const int maxn=110;const double eps=1e-8;int n,u,v,num[110];vector<int>ve[110];double a[maxn][maxn],ans[maxn];int in[maxn],d[maxn];inline void Init(){ For(i,1,n)num[i]=ve[i].size(); For(i,1,n+1)For(j,1,n+1)a[i][j]=0; for(int i=1;i<=n;i++) { a[i][i]=1; for(int j=0;j<num[i];j++) { a[i][ve[i][j]]-=1.0/d[ve[i][j]]; } if(i==1)a[i][n+1]=1; }}void gauss(){ for(int i=1;i<=n;i++) { int r=i; for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[r][i]))r=j; if(fabs(a[r][i])<eps)continue; if(r!=i)for(int j=0;j<=n+1;j++)swap(a[r][j],a[i][j]); for(int k=1;k<=n;k++) { if(k==i)continue; for(int j=n+1;j>=i;j--)a[k][j]-=a[k][i]/a[i][i]*a[i][j]; } }}int main(){ int Case=0; while(1) { read(n); if(!n)break; printf("Case #%d:\n",++Case); For(i,1,n)ve[i].clear(),d[i]=0; while(1) { read(u);read(v); if(!u&&!v)break; d[u]++; ve[v].push_back(u); } Init(); gauss(); mst(in,0); for(int i=n;i>0;i--) { if(fabs(a[i][i])<eps&&fabs(a[i][n+1])>eps)in[i]=1; for(int j=i+1;j<=n;j++) if(fabs(a[i][j])>eps&&in[j])in[i]=1; } int q,x; read(q); while(q--) { read(x); if(in[x])printf("infinity\n"); else printf("%.3lf\n",fabs(a[x][x])<eps? 0.0:a[x][n+1]/a[x][x]); } } return 0;}
UVA-10828 (概率期望+高斯消元)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。