首页 > 代码库 > BZOJ3143: [Hnoi2013]游走
BZOJ3143: [Hnoi2013]游走
3143: [Hnoi2013]游走
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1004 Solved: 438
[Submit][Status]
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
2 3
1 2
1 3
Sample Output
3.333
HINT
边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。
Source
非官方数据
题解:
这题不会做是因为没有碰见过这种题，无向图的点的期望经过次数居然是用高斯消元来解的，真是个巧妙的算法。
很容易想到贪心的来将期望经过次数小的边分上较大的标号，而边的期望经过次数又可以转化为点的期望经过次数
令x[i]为i的期望经过次数，则x[i]=sigma(x[j]/d[j]) i,j有边相连d[j]表示j的度数
特别的 我们有 x[1]=1+sigma(x[j]/d[j]) x[n]=0
所以问题就成了一个高斯消元了。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 500+100 26 27 #define maxm 250000+10000 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 41 42 using namespace std; 43 44 inline int read() 45 46 { 47 48 int x=0,f=1;char ch=getchar(); 49 50 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 51 52 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 53 54 return x*f; 55 56 } 57 int n,m,d[maxn],u[maxm],v[maxm]; 58 double a[maxn][maxn],x[maxn],w[maxm]; 59 bool f[maxn][maxn]; 60 void gauss() 61 { 62 for1(i,n-1) 63 { 64 int k=i; 65 for2(j,i+1,n)if(fabs(a[j][i])>fabs(a[k][i]))k=j; 66 for2(j,i,n+1)swap(a[i][j],a[k][j]); 67 for2(j,i+1,n) 68 { 69 double tmp=a[j][i]/a[i][i]; 70 for2(k,i,n+1)a[j][k]=a[i][k]*tmp-a[j][k]; 71 } 72 } 73 x[n]=a[n][n+1]/a[n][n]; 74 for3(i,n-1,1) 75 { 76 double tmp=0; 77 for2(j,i+1,n)tmp+=x[j]*a[i][j]; 78 x[i]=(a[i][n+1]-tmp)/a[i][i]; 79 } 80 } 81 82 int main() 83 84 { 85 86 freopen("input.txt","r",stdin); 87 88 freopen("output.txt","w",stdout); 89 90 n=read()-1;m=read(); 91 for1(i,m) 92 { 93 int x=u[i]=read(),y=v[i]=read(); 94 f[x][y]=f[y][x]=1;d[x]++;d[y]++; 95 } 96 for1(i,n) 97 { 98 a[i][i]=1.0; 99 for1(j,n)if(f[i][j])a[i][j]=-1.0/(d[j]*1.0);100 } 101 a[1][n+1]=1.0;102 gauss();103 for1(i,m)w[i]=x[u[i]]/(d[u[i]]*1.0)+x[v[i]]/(d[v[i]]*1.0);104 sort(w+1,w+m+1);105 double ans=0.0;106 for1(i,m)ans+=w[i]*(m+1-i);107 printf("%.3lf\n",ans);108 109 return 0;110 111 }
另外还要注意高斯消元的精度问题，是这样
for2(j,i+1,n) { double tmp=a[j][i]/a[i][i]; for2(k,i,n+1)a[j][k]=a[i][k]*tmp-a[j][k]; }
而不是
tmp=a[i][i]/a[j][i]
因为a[j][i]可能为0，而我们事先选取了一个绝对值最大的就是为了让a[i][i]!=0，好在这里作分母。
BZOJ3143: [Hnoi2013]游走
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。