做网站备案需要哪些材料,洛阳网站公司,德州网站建设推广价格,网站域名解析ip【BZOJ3640】JC的小苹果 Description 让我们继续JC和DZY的故事。 “你是我的小丫小苹果#xff0c;怎么爱你都不嫌多#xff01;” “点亮我生命的火#xff0c;火火火火火#xff01;” 话说JC历经艰辛来到了城市B#xff0c;但是由于他的疏忽DZY偷走了他的小苹果#x…【BZOJ3640】JC的小苹果 Description 让我们继续JC和DZY的故事。 “你是我的小丫小苹果怎么爱你都不嫌多” “点亮我生命的火火火火火火” 话说JC历经艰辛来到了城市B但是由于他的疏忽DZY偷走了他的小苹果没有小苹果怎么听歌他发现邪恶的DZY把他的小苹果藏在了一个迷宫里。JC在经历了之前的战斗后他还剩下hp点血。开始JC在1号点他的小苹果在N号点。DZY在一些点里放了怪兽。当JC每次遇到位置在i的怪兽时他会损失Ai点血。当JC的血小于等于0时他就会被自动弹出迷宫并且再也无法进入。 但是JC迷路了他每次只能从当前所在点出发等概率的选择一条道路走。所有道路都是双向的一共有m条怪兽无法被杀死。现在JC想知道他找到他的小苹果的概率。 P.S.大家都知道这个系列是提高组模拟赛所以这是一道送分题balabala Input 第一行三个整数表示nmhp。接下来一行整数第i个表示jc到第i个点要损失的血量。保证第1个和n个数为0。接下来m行每行两个整数ab表示ab间有一条无向边。 Output 仅一行表示JC找到他的小苹果的期望概率保留八位小数。 Sample Input 3 3 2 0 1 0 1 2 1 3 2 3 Sample Output 0.87500000 HINT 对于100%的数据 2n150hp10000m5000保证图联通。 题解如果没有Ai0直接DP如果hp很小直接高斯消元但是都有所以用DP高斯消元。 发现方程组中只有Ai0的点有系数Ai0的都可以直接拿过来变成常数项所以每次我们的方程组只有一列是变化的所以我们将方程组表示成AxbxA-1b。x和b都是列向量。所以我们只需要预处理出A的逆然后每次On2乘一下就行了。 矩阵求逆的方法先将(A|I)拼一起然后通过行变换将左边的A消成I右边剩下的就是A-1。 #include cstdio
#include cstring
#include iostream
#include cmath
using namespace std;
int n,m,hp;
int dam[160],pa[5010],pb[5010],d[160];
double f[160][10000],B[160],ans;
struct M
{double v[160][160];M (){memset(v,0,sizeof(v));}double* operator [](int x) {return v[x];}void I(){for(int i1;in;i) for(int j1;jn;j) v[i][j](ij)?1:0;}M getinv(){int i,j,k;M re;double t;re.I();for(i1;in;i){for(ji;jn;j) if(fabs(v[j][i])fabs(v[i][i])) for(k1;kn;k)swap(v[i][k],v[j][k]),swap(re[i][k],re[j][k]);tv[i][i];for(j1;jn;j) v[i][j]/t,re[i][j]/t;for(j1;jn;j) if(i!j){tv[j][i];for(k1;kn;k) v[j][k]-t*v[i][k],re[j][k]-t*re[i][k];}}return re;}void operator * (int x){for(int i1;in;i) for(int j1;jn;j) f[i][x]v[i][j]*B[j];}
};
M A,A1;
int rd()
{int ret0,f1; char gcgetchar();while(gc0||gc9) {if(gc-)f-f; gcgetchar();}while(gc0gc9) retret*10gc-0,gcgetchar();return ret*f;
}
int main()
{nrd(),mrd(),hprd();int i,j;for(i1;in;i) dam[i]rd();for(i1;im;i){pa[i]rd(),pb[i]rd();d[pa[i]];if(pa[i]!pb[i]) d[pb[i]];}for(i1;im;i){if(!dam[pb[i]]) A[pb[i]][pa[i]]-1.0/d[pa[i]];if(pa[i]pb[i]) continue;if(!dam[pa[i]]) A[pa[i]][pb[i]]-1.0/d[pb[i]];}for(i1;in;i) A[i][n]0;for(i1;in;i) A[i][i];A1A.getinv();for(jhp;j;j--){for(i1;in;i) B[i]0;if(jhp) B[1]1;else for(i1;im;i){if(dam[pb[i]]dam[pb[i]]jhppa[i]!n) B[pb[i]]f[pa[i]][jdam[pb[i]]]*1.0/d[pa[i]];if(pa[i]pb[i]) continue;if(dam[pa[i]]dam[pa[i]]jhppb[i]!n) B[pa[i]]f[pb[i]][jdam[pa[i]]]*1.0/d[pb[i]];}A1*j,ansf[n][j];}printf(%.8lf,ans);return 0;
} 转载于:https://www.cnblogs.com/CQzhangyu/p/7054760.html
