BZOJ 1778 [Usaco2010 Hol]Dotp 驱逐猪猡 ——期望DP
2024-10-21 18:32:56
思路和BZOJ 博物馆很像。
同样是高斯消元
#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define maxn 100005
#define eps 1e-9 double a[350][350];
double ans[350];
int n,m,p,q;
int h[maxn],to[maxn],ne[maxn],en=0,du[maxn]; void add(int a,int b)
{to[en]=b;ne[en]=h[a];h[a]=en++;du[a]++;} void Gauss()
{
F(i,1,n)
{
int tmp=i;
F(j,i+1,n) if (fabs(a[tmp][i])<fabs(a[j][i])) tmp=j;
if (tmp!=i) F(j,i,n+1) swap(a[tmp][j],a[i][j]);
F(j,i+1,n) if (j!=i)
{
double t=a[j][i]/a[i][i];
F(k,i,n+1) a[j][k]-=t*a[i][k];
}
}
D(i,n,1)
{
F(j,i+1,n)
a[i][n+1]-=a[i][j]*ans[j];
ans[i]=a[i][n+1]/a[i][i];
}
} int main()
{
scanf("%d%d%d%d",&n,&m,&p,&q);
a[1][n+1]=1.0*p/q;
F(i,1,m)
{
int x,y;scanf("%d%d",&x,&y);
du[x]++;du[y]++;
a[x][y]+=1.0; a[y][x]+=1.0;
}
F(i,1,n) F(j,1,n) if (du[j]) a[i][j]/=(double)du[j];
F(i,1,n) F(j,1,n) a[i][j]*=1.0*p/q-1;
F(i,1,n) a[i][i]+=1;
Gauss();
F(i,1,n) printf("%.9f\n",ans[i]);
}
最新文章
- VirtualBox安装MS-DOS6.22(图文教程)
- C++ 第二次课堂作业(反转链表)
- circle area
- C# 正则表达式 匹配IP地址
- 小白日记21:kali渗透测试之提权(一)--本地提权
- ☀【CSS3】切换开关
- STM32软件复位(基于库文件V3.5)
- 【转载】32复用时钟AFIO开启情况
- c# post basic 接口
- Salesforce Lightning开发学习(一)Hello World开发实践
- CSS效果:跑马灯按钮
- Python读取导入非安装文件库的方法
- PHP合并数组及去重
- SpringBoot结合Swagger2自动生成api文档
- 大话Java中的哈希(hash)结构(一)
- 高并发第十二弹:并发容器J.U.C -- Executor组件FutureTask、ForkJoin
- CentOS 7.X下 -- 配置nginx正向代理支持https
- 快速配置java环境变量
- [Android Tips] 31.如何将第三库引入的 Permission 删除掉
- xilinx DMA IP核(二) —— 文档阅读