数学期望/高斯消元/贪心
啊……用贪心的思路明显是要把经过次数期望越大的边的权值定的越小,那么接下来的任务就是求每条边的期望经过次数。
拆边为点?nonono,连接x,y两点的边的期望经过次数明显是 times[x]/du[x]+times[y]/du[y] 所以只要求出每个点的期望经过次数即可
像「随机程序」那道题一样,(马尔可夫过程?)高斯消元求解即可
特别的,第1个点是起点,方程组的常数项为1,而 「第N个点是终点,期望经过次数为0,不参与消元」 (因为走到N就停下了,不会“经过”)(这个地方WA了……sigh)
1 /**************************************************************
2 Problem: 3143
3 User: Tunix
4 Language: C++
5 Result: Accepted
6 Time:3716 ms
7 Memory:8284 kb
8 ****************************************************************/
9
10 //BZOJ 3143
11 #include<cmath>
12 #include<vector>
13 #include<cstdio>
14 #include<cstring>
15 #include<cstdlib>
16 #include<iostream>
17 #include<algorithm>
18 #define rep(i,n) for(int i=0;i<n;++i)
19 #define F(i,j,n) for(int i=j;i<=n;++i)
20 #define D(i,j,n) for(int i=j;i>=n;--i)
21 #define pb push_back
22 using namespace std;
23 int getint(){
24 int v=0,sign=1; char ch=getchar();
25 while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
26 while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
27 return v*=sign;
28 }
29 const int N=510,M=250010;
30 const double eps=1e-8;
31 typedef double Matrix[N][N];
32 /******************tamplate*********************/
33 void gauss_jordan(Matrix A,int n){
34 int r;
35 rep(i,n){
36 r=i;
37 for(int j=i+1;j<n;j++)
38 if (fabs(A[j][i]) > fabs(A[r][i])) r=j;
39 if (fabs(A[r][i]) < eps) continue;
40 if (r!=i) F(j,0,n) swap(A[r][j],A[i][j]);
41 rep(k,n) if (k!=i)
42 D(j,n,i) A[k][j]-=A[k][i]/A[i][i]*A[i][j];
43 }
44 }
45
46 Matrix A;
47 int n,m,d[N],u[M],v[M];
48 double w[M],x[N];
49 vector<int>G[N];
50
51 int main(){
52 #ifndef ONLINE_JUDGE
53 freopen("3143.in","r",stdin);
54 freopen("3143.out","w",stdout);
55 #endif
56 n=getint(); m=getint();
57 F(i,1,m){
58 u[i]=getint()-1; v[i]=getint()-1;
59 G[u[i]].pb(v[i]); G[v[i]].pb(u[i]);
60 }
61 rep(i,n) d[i]=G[i].size();
62 memset(A,0,sizeof (A));
63 rep(i,n-1){
64 A[i][i]=1;
65 rep(j,G[i].size())
66 A[i][G[i][j]]=-1.0/d[G[i][j]];
67 if (i==0) A[i][n]=1.0;
68 }
69
70 gauss_jordan(A,n);
71 rep(i,n) x[i]=A[i][n]/A[i][i];
72 x[n-1]=0;
73 F(i,1,m) w[i]=x[u[i]]/d[u[i]]+x[v[i]]/d[v[i]];
74 sort(w+1,w+m+1);
75 double ans=0.0;
76 F(i,1,m) ans+=w[m-i+1]*i;
77 printf("%.3lf\n",ans);
78 return 0;
79 }
View Code
转载于:https://www.cnblogs.com/Tunix/p/4299969.html