高斯消元又弄了半天。。

注意只要能建立矩阵,那就必定有解,所以高斯消元里可以直接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");
}
}

最新文章

  1. Jenkins 1.x权限配置(兼容2.x)
  2. 第十二篇:SOUI的utilities模块为什么要用DLL编译?
  3. 重新想象 Windows 8.1 Store Apps (84) - 图像处理的新特性, Share Contract 的新特性
  4. SAE上传web应用(包括使用数据库)教程详解及问题解惑
  5. PHP+jQuery 列表分页类 ( 支持 url 分页 / ajax 分页 )
  6. new 动态分配数组空间
  7. hdu 3669 Cross the Wall(斜率优化DP)
  8. MongoDB 数据库引用
  9. FCC(ES6写法) Map the Debris
  10. VMware vCenter Server 6.5配置群集功能
  11. java实现两个不同list对象合并后并排序
  12. JavaScript “跑马灯”抽奖活动代码解析与优化(一)
  13. Python复习基础篇
  14. [leetcode]Remove Duplicates from Sorted Array II @ Python
  15. 在使用html5的video标签播放视频时为何只有声音却没有图像
  16. LeetCode 657. Robot Return to Origin (C++)
  17. Jitsi 开源视频会议远程桌面共享&amp;&amp;文档共享工具
  18. 启动MacOS 本地服务
  19. Git介绍及基本操作
  20. ActionContext源码

热门文章

  1. 轻量级的惰性控件——ViewStub
  2. 内网渗透_win_socks代理_reGeorg+proxifier
  3. canvas的基础入门
  4. etimer
  5. php 引入其他文件中的变量
  6. GDI+用PNG图片做半透明异型窗口
  7. NX二次开发-打开part对话框UF_UI_open_part
  8. 判断语句 (a&gt;b)?a:b【转载】
  9. Putty 两步代理访问互联网
  10. 天道神诀---DHCP服务(下篇)