欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - POJ1487
题解概括
给出多个树形结构，由小写字母和数字表示，每个小写字母表示一棵小树。现在，以a为根节点，构建一棵大树，树可能是无限的。现在，一个人从树根往叶子走，直到无法走为止，得到该叶子结点上数值所表示的相应分数，人在分叉的地方走每条路的概率是一样的，求得分期望。
题解
首先通过关系建立方程组。
这个貌似很麻烦，但是很暴力，有码量没有难度。
然后高斯消元解方程。
要注意精度的问题。
解的时候要标记自由元。
也有点麻烦。
具体的看代码吧。
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long double LD;
const LD Eps=1e-8;
const int N=30;
int n,Case=0,now,pos[N];
char str[300];
bool free_x[N];
LD a[N][N],x[N];
void GetLn(){
while (getchar()!='
');
}
int Match_Pracket(int now){//now为当前要匹配的左括号位置。
int len=strlen(str+1),p=0;
for (int i=now;i<=len;i++){
if (str[i]=='(')
p++;
if (str[i]==')')
p--;
if (!p)
return i;
}
return -1;
}
bool Is_Num_Part(char ch){
return ch=='-'||('0'<=ch&&ch<='9');
}
int GetNum(int now,int &Next){//now为当前要计算的数字的最左位置，Next返回跳过数字后的位置。
int len=strlen(str+1),f=1,x=0;
if (str[now]=='-')
f=-1;
else
x=str[now]-'0';
while (Is_Num_Part(str[++now]))
x=x*10+str[now]-'0';
Next=now;
return x*f;
}
void dfs(int L,int R,LD p){
if (L>R)
return;
int tot=0,i;
for (i=L;i<=R;){
if (Is_Num_Part(str[i])){
int j,v=GetNum(i,j);
i=j,tot++;
continue;
}
if (str[i]=='('){
i=Match_Pracket(i)+1;
tot++;
continue;
}
if ('a'<=str[i]&&str[i]<='z'){
i++,tot++;
continue;
}
i++;
}
p=p/tot;
for (int i=L;i<=R;){
if (Is_Num_Part(str[i])){
int j,v=GetNum(i,j);
i=j,a[now][n]-=p*v;
continue;
}
if (str[i]=='('){
int j=Match_Pracket(i);
dfs(i+1,j-1,p);
i=j+1;
continue;
}
if ('a'<=str[i]&&str[i]<='z')
a[now][str[i]-'a']+=p;
i++;
}
}
int Gauss(){
memset(free_x,0,sizeof free_x);
memset(pos,0,sizeof pos);
int k,c;
for (k=c=0;k<n&&c<n;k++,c++){
int Mk=k;
for (int i=k+1;i<n;i++)
if (fabs(a[Mk][c])<fabs(a[i][c]))
Mk=i;
if (Mk!=k)
for (int i=c;i<=n;i++)
swap(a[Mk][i],a[k][i]);
if (fabs(a[k][c])<Eps){
k--;
free_x[c]=1;
continue;
}
pos[k]=c;
for (int i=k+1;i<n;i++)
if (fabs(a[i][c])>Eps){
for (int j=n;j>=c;j--)
a[i][j]=a[i][j]-a[k][j]/a[k][c]*a[i][c];
a[i][c]=0;
}
}
for (int i=k;i<n;i++)
if (fabs(a[i][n])>Eps)
return -1;
memset(x,0,sizeof x);
for (int i=k-1;i>=0;i--){
if (free_x[pos[i]])
continue;
LD tmp=a[i][n];
for (int j=pos[i]+1;j<n;j++){
if (fabs(a[i][j])<Eps)
continue;
if (free_x[j]){
free_x[pos[i]]=1;
break;
}
tmp-=a[i][j]*x[j];
}
if (!free_x[pos[i]])
x[pos[i]]=tmp/a[i][pos[i]];
if (fabs(x[pos[i]])<Eps)
x[pos[i]]=0;
}
return 0;
}
int main(){
while (~scanf("%d",&n)&&n){
GetLn();
memset(a,0,sizeof a);
for (now=0;now<n;now++){
a[now][now]-=1;
gets(str+1);
int pos=1;
while (str[pos]!='=')
pos++;
dfs(pos+1,strlen(str+1),1);
}
int ans=Gauss();
printf("Game %d
",++Case);
for (int i=0;i<n;i++)
if (free_x[i])
printf("Expected score for %c undefined
",i+'a');
else
printf("Expected score for %c = %.3Lf
",i+'a',x[i]);
puts("");
}
return 0;
}