哪个网站可以做经济模拟题,qq是哪个公司开发,58网络推广,网站推荐你懂我的意思吧2020知乎正题
题目链接:https://www.luogu.com.cn/problem/CF605E 题目大意
给出nnn个点的一张完全有向图#xff0c;每一天iii到jjj的路径有pi,jp_{i,j}pi,j的概率出现。 询问从111出发走到nnn在最优策略下的期望天数。 1≤n≤103,pi,i11\leq n\leq 10^3,p_{i,i}11≤n≤103,pi,i…正题
题目链接:https://www.luogu.com.cn/problem/CF605E 题目大意
给出nnn个点的一张完全有向图每一天iii到jjj的路径有pi,jp_{i,j}pi,j的概率出现。 询问从111出发走到nnn在最优策略下的期望天数。
1≤n≤103,pi,i11\leq n\leq 10^3,p_{i,i}11≤n≤103,pi,i1 解题思路
设gig_igi表示从iii到nnn的答案那么ggg满足式子 gi∑j1ngj∏gkgj(1−pj,k)×pi,j×∏gkgj(1−pi,k)g_i\sum_{j1}^{n}\frac{g_{j}}{\prod_{g_kg_j}(1-p_{j,k})}\times p_{i,j}\times \prod_{g_kg_j}(1-p_{i,k})gij1∑n∏gkgj(1−pj,k)gj×pi,j×gkgj∏(1−pi,k) 注意到里面有条件gkgjg_kg_jgkgj但是我们并不知道ggg好像就死循环了。
但是我们可以知道gng_ngn肯定是最小的而且是000然后剩下第二小的只会受到gng_ngn的影响也就是这个里面有一个的ggg是完整的。
可以猜测这个第二小的肯定是剩下的ggg里面最小的那个因为如果不是那么显然不满足我们最小化的条件从一个更大的走到了本应该可以更小的。
所以我们每次剩下的点中找到一个最小的gj∏gkgj(1−pj,k)\frac{g_{j}}{\prod_{g_kg_j}(1-p_{j,k})}∏gkgj(1−pj,k)gj来更新它对其他点的影响即可。
时间复杂度O(n2)O(n^2)O(n2) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1100;
int n;bool v[N];
double p[N][N],prod[N],f[N];
int main()
{scanf(%d,n);for(int i1;in;i){for(int j1;jn;j){scanf(%lf,p[i][j]);p[i][j]/100.0;}}if(n1)return puts(0)0;for(int i1;in;i)prod[i]1-p[i][n],f[i]1;v[n]1;while(1){double low1e9;int x;for(int i1;in;i)if(f[i]/(1-prod[i])low!v[i])lowf[i]/(1-prod[i]),xi;if(x1)return printf(%.10lf,low)0;v[x]1;for(int i1;in;i){if(v[i])continue;f[i]low*p[i][x]*prod[i];prod[i]*(1-p[i][x]);}}return 0;
}
