[HNOI2013][BZOJ3143] 游走 - 高斯消元
2024-08-26 06:02:10
题目描述
一个无向连通图,顶点从1编号到N,边从1编号到M。 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。
输入输出格式
输入格式:
第一行是正整数N和M,分别表示该图的顶点数
和边数,接下来M行每行是整数u,v(1<=u,v<=N),表示顶点u与顶点v之间存在一条边。
输入保证30%的数据满足N<=10,100%的数据满足2<=N<=500且是一个无向简单连通图。
输出格式:
仅包含一个实数,表示最小的期望值,保留3位小数。
输入输出样例
输入样例#1:
3 3
2 3
1 2
1 3
输出样例#1:
3.333
说明
边(1,2)编号为1,边(1,3)编号2,边(2,3)编号为3。
题解 :
期望dp。
贪心地想,我们肯定要往那个期望到达次数最大的边赋最小的权值;
所以问题转化成了求边的期望到达次数;
我们发现一条边连着唯一的两个点,我们要知道边的期望,首先要知道到达每个点的期望次数;
我们设f[i]表示第i个点的期望到达次数,即f[i] = ∑(f[to[i]] * deg[to[i]]) ,deg[i]表示一个点的度数;
这样我们发现可以高斯消元解出;要注意的是1号点的期望还得加上1因为从他开始必定经过;
然后求g[i],即边i的期望到达次数,g[i] = f[l[i]]/deg[l[i]] + f[r[i]]/deg[r[i]],l r表示这个边链接的两个点;
要注意如果是n号点的话,就不用考虑,因为到了n点就不会继续游走了;
然后就贪心地赋边权;
Code:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-8 int n, m;
struct edge
{
int from, to;
int nxt;
}ed[];
int deg[], head[];
int cnt;
int fr[], tt[];
inline void add(int x, int y){ed[++cnt] = (edge){x, y, head[x]};head[x] = cnt;} double g[];
double a[][];
double ans; inline void Gauss_()
{
for (register int i = ; i < n ; i ++)
{
int pivot = i ;
for (register int j = i + ; j < n ; j ++)
{
if (fabs(a[j][i] - a[pivot][i]) <= eps) pivot = j;
}
if (pivot != i)
for (register int j = ; j <= n ; j ++)
swap(a[i][j], a[pivot][j]);
for (register int j = n ; j >= i ; j --) a[i][j] /= a[i][i];
for (register int j = ; j < n ; j ++)
if (i != j)
for (register int k = n ; k >= i ; k --)
a[j][k] -= a[j][i] * a[i][k];
}
} int main()
{
scanf("%d%d", &n, &m);
for (register int i = ; i <= m; i ++)
{
int x, y;
scanf("%d%d", &x, &y);
deg[x]++, deg[y]++;
fr[i] = x, tt[i] = y;
add(x, y);
add(y, x);
} a[][n] = ;
for (register int i = ; i < n; i ++)
{
a[i][i] = ;
for (register int j = head[i]; j; j = ed[j].nxt)
{
int to = ed[j].to ;
if (to != n) a[i][to] = -1.0/deg[to];
}
} Gauss_(); for (register int i = ; i <= m ; i ++)
{
if (fr[i] != n )
g[i] += a[fr[i]][n] * (1.0 / deg[fr[i]]) ;
if (tt[i] != n)
g[i] += a[tt[i]][n] * (1.0 / deg[tt[i]]);
} sort(g + , g + + m);
for (register int i = ; i <= m ; i ++)
ans += (m - i + ) * 1.0 * g[i];
printf("%.3lf", ans); return ; }
最新文章
- Atitit.研发团队的管理原则---立长不立贤与按资排辈原则
- 2014 Multi-University Training Contest 9#1009
- SQL Server中的日期格式化
- ubuntu 防火墙 添加策略 解决mysql远程访问问题
- hdu 1885 Key Task
- Js 返回页面 or 跳转页面
- jquery toggle 替换的实现
- python-shutil学习
- django(models)视图与html 简单的操作
- python入门(四)
- Rocketlab公司火箭Electron介绍
- 函数重载(overload)
- 【TJOJI\HEOI2016】求和
- Quick Find (QF)
- random模块,time模块,os模块,sys模块
- Redis 复制原理及分析
- Windows 2008安装Oracle10g提示操作系统版本检查未通过
- Swift3.0生成二维码、扫描二维码、相册读取二维码,兼容iOS7(结合ZXingObjC)
- 20145221 《Java程序设计》第十周学习总结
- oracle中将number类型毫秒值转为时间类型
热门文章
- Https与Http的区别以及Https的解说
- 一步步到IOC
- 第一次作业:使用Packet Tracer分析HTTP包
- Docker在IDEA中的使用以及如何部署到服务器
- 02 (OC)* ViewController 的声明周期
- Android服务之混合方式开启服务
- 实操:Could not autowire No beans of &#39;FastDFS Client&#39; type found 的解决方法
- netCDF4 not installed properly - DLL load failed (netCDF4安装问题)
- 遗传编程(GA,genetic programming)算法初探,以及用遗传编程自动生成符合题解的正则表达式的实践
- 修改zabbix的端口号