CC和他的AE86

题意：

概率dp

场上本来是用矩阵写的，无奈出了点偏差一直过不了样例！！！

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=55;
 5 const int maxe=3600;
 6 struct Matrix{
 7     int n;
 8     double m[maxn][maxn];
 9 
10     void init(int sz){
11         n=sz;
12         for(int i=0;i<n;i++){
13             for(int j=0;j<n;j++){
14                 m[i][j]=0.0;
15             }
16         }
17     }
18     Matrix(int sz){init(sz);}
19 
20     void set_I(){
21         for(int i=0;i<n;i++) m[i][i]=1.0;
22     }
23 
24     Matrix operator* (const Matrix &a)const{
25         Matrix ans(n);
26         for(int k=0;k<n;k++){
27             for(int i=0;i<n;i++){
28                 for(int j=0;j<n;j++){
29                     ans.m[i][j]+=m[i][k]*a.m[k][j];
30                 }
31             }
32         }
33         return ans;
34     }
35 };
36 
37 int deg[maxn];
38 int u[maxe],v[maxe];
39 
40 
41 int main(){
42     int n,m;
43     while(scanf("%d%d",&n,&m)!=EOF){
44         memset(deg,0,sizeof(deg));
45         for(int i=0;i<m;i++){
46             scanf("%d%d",&u[i],&v[i]);
47             u[i]--;v[i]--;
48             deg[u[i]]++;
49             deg[v[i]]++;
50         }
51         int q;
52         scanf("%d",&q);
53         while(q--){
54             int ss,ee,d;
55             scanf("%d%d%d",&ss,&ee,&d);
56             ss--;ee--;
57             Matrix base(n);
58             for(int i=0;i<m;i++){
59                 int x=u[i],y=v[i];
60                 base.m[x][y]=1.0/deg[x];
61                 base.m[y][x]=1.0/deg[y];
62                 if(x==ee) base.m[x][y]=0;
63                 if(y==ee) base.m[y][x]=0;
64             }
65             Matrix ans(n);
66             ans.set_I();
67             while(d){
68                 if(d&1) ans=ans*base;
69                 d>>=1;
70                 base=base*base;
71             }
72             double res=0;
73             for(int i=0;i<n;i++){
74                 if(i!=ee) res+=ans.m[ss][i];
75             }
76             printf("%.8lf
",1.0-res);
77         }
78     }
79 }

View Code

矩阵好像慢很多，下面dalao写的还没仔细看~

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef unsigned long long ull;
 5 const int maxn=55;
 6 const int maxm=1005;
 7 const int maxe=7000005;
 8 const int inf=0x3f3f3f3f;
 9 int n,m,k;
10 double dp[maxn][maxn][105];
11 vector<int> e[maxn];
12 bool vis[maxn][maxn][105];
13 double DP(int u,int to,int times){
14     if(times==-1)return 0;
15     if(vis[u][to][times])return dp[u][to][times];
16     if(u==to)return 1;
17     int sz=e[u].size();
18     double ans=0;
19     for(int i=0;i<sz;i++){
20         ans+=DP(e[u][i],to,times-1)/sz;
21     }
22     vis[u][to][times]=1;
23     return dp[u][to][times]=ans;
24 }
25 
26 int main(){
27     int a,b,q,c;
28     while(~scanf("%d%d",&n,&m)){
29             for(int i=1;i<=n;i++)e[i].clear();
30             memset(vis,0,sizeof(vis));
31             for(int i=0;i<m;i++){
32                 scanf("%d%d",&a,&b);
33                 e[a].push_back(b);
34                 e[b].push_back(a);
35             }
36             scanf("%d",&q);
37             for(int i=0;i<q;i++){
38                 scanf("%d%d%d",&a,&b,&c);
39                 printf("%.10lf
",DP(a,b,c));
40             }
41     }
42     return 0;
43 }

dalao

哎，前三场个人赛全部爆炸！每场都会卡在一个小bug上无法自拔~~ 今天这场还差点爆零=_=

明天还有最后一场，但愿不爆零吧=_=

其实一个假期下来感觉已经提高不少了，一比才知道差距啊。。。。。。