期望dp+高斯消元+bfs——hdu4418
2024-09-06 10:54:08
高斯消元又弄了半天。。
注意只要能建立矩阵,那就必定有解,所以高斯消元里可以直接return 1
#include<bits/stdc++.h>
using namespace std; const int maxn = ;
const double esp = 1e-; int n,m,x,y,d;
double p[maxn],a[maxn][maxn],b[maxn];
int equ,var; int Gauss(){
for(int i=;i<n;i++){
int maxr=i;
for(int j=i+;j<n;j++)
if(fabs(a[j][i])>fabs(a[maxr][i]))
maxr=j;
if(fabs(a[maxr][i])<esp)continue;
if(maxr!=i)
swap(a[maxr],a[i]);swap(b[maxr],b[i]); for(int j=i+;j<n;j++){
if(fabs(a[j][i])<esp)continue;
double rate=a[j][i]/a[i][i];
for(int k=i;k<n;k++)
a[j][k]-=rate*a[i][k];
b[j]-=rate*b[i];
}
}
for(int i=n-;i>=;i--){
if(fabs(a[i][i])<esp)continue;
for(int j=i+;j<n;j++)
b[i]-=a[i][j]*b[j];
b[i]/=a[i][i];
}
return ;
} int id[maxn],cnt;
void bfs(int s){
memset(id,-,sizeof id);
cnt=;
queue<int>q;
q.push(s);id[s]=cnt++;
while(q.size()){
int x=q.front();q.pop();
for(int i=;i<=m;i++){
if(fabs(p[i])<esp)continue;
int y=(x+i)%n;
if(id[y]==-)
q.push(y),id[y]=cnt++;
}
}
} int main(){
int t;cin>>t;
while(t--){
scanf("%d%d%d%d%d",&n,&m,&y,&x,&d); for(int i=;i<=m;i++)
scanf("%lf",&p[i]),p[i]/=;
if(x==y){puts("0.00");continue;} n=*(n-);
if(d==)x=n-x;
bfs(x);
if(id[y]==- && id[n-y]==-){
puts("Impossible !");continue;
}
equ=var=cnt; memset(a,,sizeof a);
memset(b,,sizeof b);
for(int i=;i<n;i++){
if(id[i]==-)continue;
a[id[i]][id[i]]=;
if(i==y || i==n-y)continue;//到了终点y
for(int j=;j<=m;j++){
int y=(i+j)%n;
if(id[y]!=-){
a[id[i]][id[y]]-=p[j];
b[id[i]]+=j*p[j];
}
}
}
if(Gauss())
printf("%.2lf\n",b[id[x]]);
else printf("Impossible !\n");
}
}
最新文章
- Jenkins 1.x权限配置(兼容2.x)
- 第十二篇:SOUI的utilities模块为什么要用DLL编译?
- 重新想象 Windows 8.1 Store Apps (84) - 图像处理的新特性, Share Contract 的新特性
- SAE上传web应用(包括使用数据库)教程详解及问题解惑
- PHP+jQuery 列表分页类 ( 支持 url 分页 / ajax 分页 )
- new 动态分配数组空间
- hdu 3669 Cross the Wall(斜率优化DP)
- MongoDB 数据库引用
- FCC(ES6写法) Map the Debris
- VMware vCenter Server 6.5配置群集功能
- java实现两个不同list对象合并后并排序
- JavaScript “跑马灯”抽奖活动代码解析与优化(一)
- Python复习基础篇
- [leetcode]Remove Duplicates from Sorted Array II @ Python
- 在使用html5的video标签播放视频时为何只有声音却没有图像
- LeetCode 657. Robot Return to Origin (C++)
- Jitsi 开源视频会议远程桌面共享&;&;文档共享工具
- 启动MacOS 本地服务
- Git介绍及基本操作
- ActionContext源码