首页 > 其他 > 详细

bzoj 3143: [Hnoi2013]游走

时间:2017-02-20 07:42:39      阅读:269      评论:0      收藏:0      [点我收藏+]

 (就不说一开始做的辛酸泪了)

因为这是个无向图,还有环,BT,所以期望是不能直接去求的2333

所以,根据每个点的情况,看一下可以从哪些点到这个点,然后根据那个点到这个点的概率,就可以写出这个点的方程2333

写出所有方程,就可以高斯消元了2333

对于为什么要把a[1][n+1]给设成-1不是很懂,可能是表示的最开始1点的什么东西,期望==1?(记住吧,(真做题又不一定能想出来2333,没什么好担心的2333))

有了点的期望,边的期望就好解了,然后贪心一下就ok

 1 #include<bits/stdc++.h>
 2 #define N 100005
 3 #define LL long long
 4 #define inf 0x3f3f3f3f
 5 #define ls c[x][0]
 6 #define rs c[x][1]
 7 #define eps 1e-10  //这eps太扯淡了2333 
 8 using namespace std;
 9 inline int ra()
10 {
11     int x=0,f=1; char ch=getchar();
12     while (ch<0 || ch>9) {if (ch==-) f=-1; ch=getchar();}
13     while (ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}
14     return x*f;
15 }
16 int n,m,d[505];  
17 struct node{ int x,y; double z; }e[505*505]; double a[550][550];  
18 void guass()
19 {
20     for (int j=1; j<=n; j++)
21     {
22         bool flag=0; int pos;
23         for (int i=j; i<=n; i++) if (fabs(a[i][j])>eps) {pos=i; flag=1; break;}
24         if (!flag) continue; if (pos!=j) swap(a[j],a[pos]);
25         for (int i=j+1; i<=n; i++)
26             if (fabs(a[i][j])>eps)
27             {
28                 double t=a[i][j]/a[j][j];
29                 for (int k=j; k<=n+1; k++)
30                     a[i][k]-=t*a[j][k];
31             }
32     }
33     for (int i=n; i>=1; i--)
34     {
35         for (int j=i+1; j<=n; j++)
36             a[i][n+1]-=a[i][j]*a[j][n+1];
37         a[i][n+1]/=a[i][i];
38     }
39 }
40 bool cmp(node a, node b){return a.z>b.z;}
41 int main()
42 {
43     n=ra(); m=ra();
44     for (int i=1; i<=m; i++)
45         d[e[i].x=ra()]++,d[e[i].y=ra()]++;
46     for (int i=1; i<=m; i++)
47     {
48         a[e[i].x][e[i].y]+=1.0/d[e[i].y];
49         a[e[i].y][e[i].x]+=1.0/d[e[i].x];
50     }
51     for (int i=1; i<=n; i++) a[n][i]=0,a[i][i]=-1;
52     a[1][n+1]=-1; 
53     guass(); 
54     for (int i=1; i<=m; i++)
55         e[i].z=a[e[i].x][n+1]/d[e[i].x]+a[e[i].y][n+1]/d[e[i].y];
56     sort(e+1,e+m+1,cmp);
57     double ans=0;
58     for (int i=1; i<=m; i++)
59         ans+=i*e[i].z;
60     printf("%.3lf",ans);
61 }

 

bzoj 3143: [Hnoi2013]游走

原文:http://www.cnblogs.com/ccd2333/p/6418037.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!