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;
}

  

上一篇:<关于数据仓库>基于docker的Mysql与Hadoop/Hive之间的数据转移 (使用Apache Sqoop™)


下一篇:用命令行在github新建一个项目