Description
一個無向連通圖，頂點從1編号到N，邊從1編号到M。
小Z在該圖上進行随機遊走，初始時小Z在1号頂點，每一步小Z以相等的機率随機選 擇目前頂點的某條邊，沿着這條邊走到下一個頂點，獲得等于這條邊的編号的分數。當小Z 到達N号頂點時遊走結束，總分為所有獲得的分數之和。
現在，請你對這M條邊進行編号，使得小Z獲得的總分的期望值最小。
Input
第一行是正整數N和M，分别表示該圖的頂點數 和邊數，接下來M行每行是整數u，v(1≤u,v≤N)，表示頂點u與頂點v之間存在一條邊。 輸入保證30%的資料滿足N≤10，100%的資料滿足2≤N≤500且是一個無向簡單連通圖。
Output
僅包含一個實數，表示最小的期望值，保留3位小數。
Sample Input
3 3
2 3
1 2
1 3
Sample Output
3.333
HINT
邊(1,2)編号為1，邊(1,3)編号2，邊(2,3)編号為3。
經某位大神的講解，瞬間領悟了，原來這麼簡單
設點i的期望經過次數為f[i]，那麼就有f[i]=∑f[j]/d[j]（j與i之間有邊相連，d[j]為點j關聯的邊數）
因為一開始在點1上，是以f[1]還要加上一個1
又因為到了n點就結束，是以點n不能為其他點提供期望經過次數，設f[n]=0
是以我們可以列出n-1個方程，一共有n-1個變量，可以解出n-1個點的期望經過次數
然後我們可以求出每條邊的期望經過次數
對于每一條邊（v，u）它的期望經過次數為f[v]/d[i]+f[u]/d[v]
再排個序，根據排序不等式我們知道，倒序才是最小的，倒着标号，然後求和得到最小期望總分
最開始在BZOJ上過了，Wikioi上沒過
我以為是精度太高了，把extended改成了double，還是沒過
後來下了标程才知道，原來在判斷是否為0時用到了精度判斷
在BZOJ上不能用精度判斷，在wikioi上必須用精度判斷
注意細節啊
1 const
2 eps=1e-7;
3 var
4 n,m:longint;
5 d:array[0..510]of longint;
6 f:array[0..510,0..510]of extended;
7 v,u:array[0..250000]of longint;
8 exp:array[0..250000]of extended;
9 ans:extended;
10
11 procedure swap(var x,y:extended);
12 var
13 t:extended;
14 begin
15 t:=x;
16 x:=y;
17 y:=t;
18 end;
19
20 procedure sort(l,r:longint);
21 var
22 i,j:longint;
23 z:extended;
24 begin
25 i:=l;
26 j:=r;
27 z:=exp[(l+r)>>1];
28 repeat
29 while exp[i]>z do
30 inc(i);
31 while exp[j]<z do
32 dec(j);
33 if i<=j then
34 begin
35 swap(exp[i],exp[j]);
36 inc(i);
37 dec(j);
38 end;
39 until i>j;
40 if j>l then sort(l,j);
41 if i<r then sort(i,r);
42 end;
43
44 procedure main;
45 var
46 i,j,k:longint;
47 s:extended;
48 begin
49 read(n,m);
50 for i:=1 to m do
51 begin
52 read(v[i],u[i]);
53 inc(d[v[i]]);
54 inc(d[u[i]]);
55 end;
56 for i:=1 to n-1 do
57 f[i,i]:=-1;
58 for i:=1 to m do
59 begin
60 f[v[i],u[i]]:=f[v[i],u[i]]+1/d[u[i]];
61 f[u[i],v[i]]:=f[u[i],v[i]]+1/d[v[i]];
62 end;
63 f[1,n]:=-1;
64 for i:=2 to n-1 do
65 f[i,n]:=0;
66 for i:=1 to n-2 do
67 begin
68 for j:=i to n-1 do
69 if f[j,i]<>0 then break;
70 for k:=i to n do
71 swap(f[i,k],f[j,k]);
72 for j:=i+1 to n-1 do
73 if abs(f[j,i])-eps>0 then
74 begin
75 s:=f[j,i]/f[i,i];
76 f[j,i]:=0;
77 for k:=i+1 to n do
78 f[j,k]:=f[j,k]-s*f[i,k];
79 end;
80 end;
81 for i:=n-1 downto 1 do
82 begin
83 for j:=i+1 to n-1 do
84 f[i,n]:=f[i,n]-f[j,0]*f[i,j];
85 f[i,0]:=f[i,n]/f[i,i];
86 end;
87 for i:=1 to m do
88 begin
89 exp[i]:=exp[i]+f[v[i],0]/d[v[i]];
90 exp[i]:=exp[i]+f[u[i],0]/d[u[i]];
91 end;
92 sort(1,m);
93 for i:=1 to m do
94 ans:=ans+i*exp[i];
95 write(ans:0:3);
96 end;
97
98 begin
99 main;
100 end. View Code
轉載于:https://www.cnblogs.com/Randolph87/p/3582372.html