BZOJ 3143 游走(高斯消元)

题意:一个无向连通图,顶点从1编号到n,边从1编号到m。小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达n号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这m条边进行编号,使得小Z获得的总分的期望值最小。

思路:显然,需要求出每条边的期望经过次数,然后排序贪心赋值即可,但是每条边的期望经过次数是什么呢?

是 E(e)=E(u)/D(u) + E(v)/D(v) (u,v∈e)

所以做法就是先求出每个点的期望经过次数,还有,就是对于第n个点,它的期望在最后统计的时候要看做0,因为到了n点就不会再出来了。

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<iostream>
 6 struct edge{
 7     int u,v;
 8     double w;
 9 }e[500005];
10 int n,m,du[500005],go[1005][1005];
11 double a[1010][1010],p[500005];
12 bool Cmp(edge q,edge w){
13     return q.w>w.w;
14 }
15 void gauss(){
16     int to,now=1;
17     for (int i=1;i<=n;i++){
18         for (to=now;to<=n;to++) if (a[to][i]!=0) break;
19         if (to>n) continue;
20         if (to!=now) for (int j=1;j<=n+1;j++) std::swap(a[now][j],a[to][j]);
21         double t=a[now][i];
22         for (int j=1;j<=n+1;j++) a[now][j]/=t;
23         for (int j=1;j<=n;j++)
24          if (j!=now){
25                 t=a[j][i];
26                 for (int k=1;k<=n+1;k++)
27                  a[j][k]-=t*a[now][k];
28         }
29         now++;
30     }
31 }
32 int main(){
33     scanf("%d%d",&n,&m);
34     int tot=0;
35     for (int i=1;i<=m;i++){
36         int x,y;
37         scanf("%d%d",&x,&y);
38         if (x==y) continue;
39         e[++tot].u=x;e[tot].v=y;
40         go[x][++go[x][0]]=y;
41         go[y][++go[y][0]]=x;
42         du[e[tot].u]++;
43         du[e[tot].v]++;
44     }
45     m=tot;
46     for (int i=1;i<n;i++) a[i][i]=1;
47     for (int i=1;i<n;i++){
48         for (int j=1;j<=go[i][0];j++){
49             int t=go[i][j];
50             if (t==n) continue;
51             a[i][t]-=1.0/du[t];
52         }
53     }
54     n--;
55     a[1][n+1]=1;
56     gauss();
57     for (int i=1;i<=n;i++) p[i]=a[i][n+1];
58     for (int i=1;i<=m;i++)
59      e[i].w=((double)p[e[i].u])/((double)du[e[i].u])+((double)p[e[i].v])/((double)du[e[i].v]);
60     std::sort(e+1,e+1+m,Cmp);
61     double ans=0;
62     for (int i=1;i<=m;i++) ans+=e[i].w*i;
63     printf("%.3f\n",ans);
64 }
时间: 05-24

BZOJ 3143 游走(高斯消元)的相关文章

BZOJ 3143 HNOI2013 游走 高斯消元 期望

这道题是我第一次使用高斯消元解决期望类的问题,首发A了,感觉爽爽的.... 中文题目,就不翻大意了,直接给原题: 一个无向连通图,顶点从1编号到N,边从1编号到M. 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数.当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和. 现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小. 输出最小的总分期望值. Solution: 这题贪心很明显

【BZOJ-3143】游走 高斯消元 + 概率期望

3143: [Hnoi2013]游走 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 2264  Solved: 987[Submit][Status][Discuss] Description 一个无向连通图,顶点从1编号到N,边从1编号到M. 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数.当小Z 到达N号顶点时游走结束,总分为所有获得的分数

BZOJ 3143: [Hnoi2013]游走( 高斯消元 )

我一开始的想法是设f(x)表示点x到N路径的期望长度, 那么f(u) = (∑f(v)+w(u,v)) / degreeu, f(N)=0, 我们代入入消元应该可以得到f(1)关于各条边长的关系式f(1)=∑we..然后贪心, 按照他们的系数来给边权...但是不会实现..但是我感觉是可行的..PoPoQQQ题解:http://blog.csdn.net/PoPoQQQ/article/details/42234607 ---------------------------------------

BZOJ 3143 游走 | 数学期望 高斯消元

啊 我永远喜欢期望题 BZOJ 3143 游走 题意 有一个n个点m条边的无向联通图,每条边按1~m编号,从1号点出发,每次随机选择与当前点相连的一条边,走到这条边的另一个端点,一旦走到n号节点就停下.每经过一条边,要付出这条边的编号这么多的代价.现将所有边用1~m重新编号,使总代价的期望最小,求这个最小值. 题解 我们可以求出每条边的期望经过次数,然后贪心地让经过次数多的边编号小即可. 直接用边来列方程求经过次数似乎列不出来,我们借助点来列方程. 设x[u]为从某个点出发的次数的期望,v为与u

BZOJ 3759 Hungergame 博弈论+高斯消元

题目大意:给定一些箱子,每个箱子里有一些石子,两个人轮流操作,每个人可以进行以下操作之一: 1.打开任意多的箱子 2.从一个打开的箱子中拿走任意多的石子 不能操作者判负,求先手是否必胜 先手必胜的状态为:给出的数字集合存在一个异或和为零的非空子集,则先手必胜 证明: 首先我们有状态A:当前的所有打开的箱子中的石子数异或和为零,且所有关闭的箱子中的石子数的集合中不存在一个异或和为零的非空子集 易证A状态时先手必败 先手有两种操作: 1.从一个打开的箱子中拿走一些石子 那么根据Nim的结论 后手可以

BZOJ 2115 [Wc2011] Xor 高斯消元

题意:链接 方法:高斯消元 解析:不怎么好想的一道题,不过如果想到的话那就是水题一个了. 首先明确一些概念 简单路径:顶点序列中顶点不重复出现的路径. 简单环:在一个回路中,若除第一个与最后一个顶点外,其余顶点不重复出现的回路称为简单回路(简单回路). 然后呢明确题里说的是什么? 找一条1到n的路径使得所有路径上的边权异或和最大. 那么我们可以拆分一下,这条1到n的路径我们看做两个部分组成:一条简单路径从1到n,以及任意简单环. 这样就比较明了了,然后我们发现,这个简单路径其实找一条就可以了,由

BZOJ 3143 游走

ans=Σf[e]*w[e],其中f[e]表示e期望经过的次数. 卡精度差评.差评.差评. 但是高消写法得改改了.... #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxv 1050 #define maxe 1000050 #define eps 1e-10 using namespace s

BZOJ 2115: [Wc2011] Xor [高斯消元XOR 线性基 图]

啦啦啦 题意: N 个点M条边的边带权的无向图,求1到n一条XOR和最大的路径 感觉把学的东西都用上了.... 1到n的所有路径可以由一条1到n的简单路径异或上任意个简单环得到 证明: 如果环与路径有交,异或后那块交就没了,相当于那块走了环上的路径: 如果环与路径没交,就是走到环上走一圈在回来,一去一回其他的地方又没了. 求一棵生成树,然后每一条非树边构成一个环,一共$m-n+1$个环 然后答案就是任取一些环的异或和与1到n路径异或和异或的最大值啦 实现上注意: 1.求生成树和简单环的异或和一遍

bzoj 2784 时间流逝 —— 树上高斯消元

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2784 其实转移是一棵树,从根到一个点表示一种能量圈状态,当能量值大于 T 是停止,也就是成为叶子: 点数大约是整数划分,据说是 1.2e6 左右,可以 dfs: 设 \( d[x] \) 是儿子数,则 \( f[x] = p*(f[fa]+1) + (1-p) \frac{\sum\limits_{v \in son}(f[v]+1)}{d[x]} \) 仍然设 \( f[x] = K[x