poj 1487 Single-Player Games

主要考察表达式的解析和高斯消元！！！
  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<algorithm>
  4 #include<iomanip>
  5 #include<cmath>
  6 #include<cstring>
  7 #include<vector>
  8 #define ll __int64
  9 #define pi acos(-1.0)
 10 #define SIZE 1024
 11 using namespace std;
 12 const double eps=1e-8;
 13 inline bool zero(double x)
 14 {
 15     return fabs(x)<eps;
 16 }
 17 struct node
 18 {
 19     int type,val;
 20     node(){}
 21     node(int _type,int _val){
 22         type=_type;
 23         val=_val;
 24     }
 25 }an[SIZE];
 26 vector<int> g[SIZE];
 27 double mat[32][32];
 28 int n,ind;
 29 char *p;
 30 void build(int now)
 31 {
 32     int t,m;
 33     while(*p){
 34         while(*p==' '&&*p) p++;
 35         if(!*p) break;
 36         if((*p>='0'&&*p<='9')||*p=='-'){
 37             ind++;
 38             sscanf(p,"%d%n",&t,&m);
 39             p+=m;
 40             an[ind]=node(0,t);
 41             g[now].push_back(ind);
 42         }
 43         else if(*p=='(')
 44         {
 45             ind++;
 46             an[ind]=node(-1,0);
 47             p++;
 48             g[now].push_back(ind);
 49             build(ind);
 50         }
 51         else if(*p==')')
 52         {
 53             p++;
 54             return;
 55         }
 56         else{
 57             ind++;
 58             an[ind]=node(1,*p-'a');
 59             p++;
 60             g[now].push_back(ind);
 61         }
 62     }
 63 }
 64 void toMat(int now,double tp,int var)
 65 {
 66     double p;
 67     if(g[now].size()) p=tp/g[now].size();
 68     for(int i=0;i<(int)g[now].size();i++){
 69         int x=g[now][i];
 70         if(an[x].type==-1)
 71             toMat(x,p,var);
 72         else{
 73             if(an[x].type==0)
 74                 mat[var][n]+=an[x].val*p;
 75             else{
 76                 mat[var][an[x].val]-=p;
 77             }
 78         }
 79     }
 80 }
 81 void init()
 82 {
 83     ind=0;
 84     memset(an,0,sizeof(an));
 85     for(int i=0;i<SIZE;i++) g[i].clear();
 86 }
 87 void Gauss_line(int a,int b,int col)
 88 {
 89     double mul_a=mat[a][col];
 90     double mul_b=mat[b][col];
 91     for(int i=0;i<=n;i++)
 92         mat[b][i]=mat[b][i]-mat[a][i]*mul_b/mul_a;
 93 }
 94 void Gauss()
 95 {
 96     for(int row=0,col=0;row<n&&col<n;row++,col++){
 97         int ptr=-1;
 98         for(int i=row;i<n;i++)
 99             if(!zero(mat[i][col])){
100                 ptr=i;
101                 break;
102             }
103         if(ptr==-1) continue;
104         else{
105             for(int i=0;i<=n;i++)
106                 swap(mat[row][i],mat[ptr][i]);
107             for(int i=0;i<n;i++)
108                 if(i!=row)
109                     Gauss_line(row,i,col);
110         }
111     }
112 }
113 double getans(int x)
114 {
115     return mat[x][n]/mat[x][x];
116 }
117 bool check(int x)
118 {
119     for(int i=0;i<n;i++)
120         if(i!=x&&!zero(mat[x][i]))
121             return false;
122     return !zero(mat[x][x]);
123 }
124 int main(){
125     int m,i,j,t=1;
126     char cmd[SIZE];
127     while(cin>>n&&n){
128         memset(mat,0,sizeof(mat));
129         printf("Game %d
",t++);
130         for(int i=0;i<n;i++){
131             init();
132             do{
133                 gets(cmd);
134             }while(*cmd=='');
135             p=cmd;
136             while(*p!='(') p++;
137             build(0);
138             toMat(0,1.,i);
139             mat[i][i]+=1.0;
140         }
141         Gauss();
142         for(i=0;i<n;i++){
143             if(check(i))
144                 printf("Expected score for %c = %.3lf
",'a'+i,getans(i));
145             else
146                 printf("Expected score for %c undefined
",'a'+i);
147         }
148         printf("
");
149     }
150     return 0;
151 }
View Code