网站设计主题,河北省建设招标网站,百度关键词优化方法,电商网站策划题干#xff1a;
随着新版百度空间的下线#xff0c;Blog宠物绿豆蛙完成了它的使命#xff0c;去寻找它新的归宿。
给出一个有向无环的连通图#xff0c;起点为1终点为N#xff0c;每条边都有一个长度。绿豆蛙从起点出发#xff0c;走向终点。 到达每一个顶点时#x…题干
随着新版百度空间的下线Blog宠物绿豆蛙完成了它的使命去寻找它新的归宿。
给出一个有向无环的连通图起点为1终点为N每条边都有一个长度。绿豆蛙从起点出发走向终点。 到达每一个顶点时如果有K条离开该点的道路绿豆蛙可以选择任意一条道路离开该点并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道从起点走到终点的所经过的路径总长度期望是多少
Input
第一行: 两个整数 N M代表图中有N个点、M条边 第二行到第 1M 行: 每行3个整数 a b c代表从a到b有一条长度为c的有向边
Output 从起点到终点路径总长度的期望值四舍五入保留两位小数。
Sample Input
4 4
1 2 1
1 3 2
2 3 3
3 4 4Sample Output
7.00
Hint 对于100%的数据 N100000M2*N
解题报告
根据期望的线性性可以转化成每条边被走过的次数的和。也就是每条边的概率乘以该边的边权求和就是答案。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
int head[MAX],n,m,tot,in[MAX],out[MAX];
double p[MAX],ans;
struct Edge {int u,v,w;int ne;
} e[MAX];
void add(int u,int v,int w) {e[tot].u u;e[tot].v v;e[tot].w w;e[tot].ne head[u];head[u] tot;
}
int main()
{tot0;memset(head,-1,sizeof head);cinnm;for(int a,b,c,i 1; im; i) scanf(%d%d%d,a,b,c),add(a,b,c),out[a],in[b]; queueint q;q.push(1);p[1]1;while(q.size()) {int cur q.front();q.pop();for(int i head[cur]; ~i; i e[i].ne) {int v e[i].v,u e[i].u;in[v]--;if(!in[v]) q.push(v);p[v] p[u]/out[u];ans (p[u]/out[u]) * e[i].w;}}printf(%.2f\n,ans);return 0 ;
}总结
当然这题也可以像【POJ - 2096】Collecting Bugs概率dp这题一样用dp[i]代表从i这个点开始走到n号节点的平均边数然后dp[n]0dp[1]就是答案。
但是这题没必要因为那道题是转化成DAG图之后你知道每条边转化的概率所以可以直接dp但是这题你刚开始并不知道每条边被走过的概率是多少比如这个图就不知道这一点没所以没法用这个信息。
所以这题如果非要用这种方法解题那首先先预处理出来每条边的概率
然后就可以用那种dp的方式求解了。
