足球竞猜网站开发,网站推广报价,网站定制营销,多城市网站设计题目链接
题面链接
题意
给定一个无向图#xff0c;你需要从11点出发到达n role=presentation style=position: relative;nn点#xff0c;你在每一点的时候#xff0c;使用11个单位的代价，随机得到相邻点的票，但是你可以选择留在原地…题目链接
题面链接
题意
给定一个无向图你需要从111点出发到达n" role="presentation" style="position: relative;">nnn点你在每一点的时候使用111个单位的代价，随机得到相邻点的票，但是你可以选择留在原地，也可以选择使用掉这张票，问到达n" role="presentation" style="position: relative;">nnn点的最小代价的方案的期望是多少。
题解
我们先假定在最优方案下从每个点xxx出发，到达n" role="presentation" style="position: relative;">nnn点的代价的期望为exexe_x那么显然我们可以列出方程ex∑min(ex,ey)degx1ex∑min(ex,ey)degx1e_x = \frac{\sum{min(e_x,e_y)}}{deg_x}+1其中yyy与x" role="presentation" style="position: relative;">xxx节点相连。初值dpn0dpn0dp_n = 0。
借鉴GXZlegendGXZlegendGXZlegend的一句话遇见“初始值只有一个点的dpdpdp值确定,其他点的dpdpdp值依赖于已经计算出来的点的dpdpdp值”这种类型的题往往考虑使用最短路的方式转移。
观察方程如果我们按照计算出来的exexe_x从小到大的方式遍历的话那么先计算出来的exexe_x一定不会再被后计算出来的值更新满足跟最短路一样的性质。
我们一开始假定所有的ex|x!ninfex|x!ninfe_{x|x!=n}=inf,并且en0en0e_n = 0每个点的min(ex,ey)min(ex,ey)min(e_x,e_y)都取exexe_x。
那么我们模拟一下这个转移过程当前从堆里取出的点是uuu，相邻的点有v" role="presentation" style="position: relative;">vvv,我们发现vvv是第一次被更新，因为ev=inf" role="presentation" style="position: relative;">ev=infev=infe_v = inf满足eveueveue_v > e_u那么vvv就要被更新，即根据方程ev=(degv#x2212;1)ev+eudegv+1" role="presentation" style="position: relative;">ev=(degv−1)ev+eudegv+1ev=(degv−1)ev+eudegv+1e_v = \frac{(deg_v-1)e_v + e_u}{deg_v}+1那么eveudegveveudegve_v = e_u+deg_v。 如果接下来某次取出的点是ppp，相邻的点还有v" role="presentation" style="position: relative;">vvv并且evepevepe_v > e_p那么eveve_v就要被二次更新了也就是ev(degv−2)eveuepdegv1ev(degv−2)eveuepdegv1e_v = \frac{(deg_v-2)e_v+e_u+e_p}{deg_v}+1那么eveuepdegv2eveuepdegv2e_v = \frac{e_u+e_p+deg_v}{2}。依次类推。
代码
#include iostream
#include queue
#include vector
using namespace std;
const int maxn 300007;
const double inf 1e9;
int n,m;
vectorint G[maxn];
typedef pairdouble,int pii;
priority_queuepii,vectorpii,greaterpii Q;
double dp[maxn];
int deg[maxn],vis[maxn];
int usedeg[maxn];
void dij(){for(int i 1;i n;i) dp[i] inf;Q.push({0,n});vis[n] 1;while(!Q.empty()){pii p Q.top();Q.pop();int u p.second;double nowdp p.first;if(nowdp dp[u]) continue;for(int v:G[u]){if(!vis[v]){vis[v] 1;usedeg[v] 1;dp[v] nowdpdeg[v];Q.push({dp[v],v});}else if(nowdp dp[v]){double c dp[v]*usedeg[v]-deg[v];usedeg[v];dp[v] (cnowdpdeg[v])/usedeg[v];Q.push({dp[v],v});}}}
}int main(){cinnm;for(int i 0;i m;i){int u,v;scanf(%d%d,u,v);G[u].push_back(v);G[v].push_back(u);deg[u] ,deg[v] ;}dij();printf(%.12lf\n,dp[1]);}
