首页 > 试题广场 >

图上行走

[编程题]图上行走

热度指数：108 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个有向无环的连通图，起点为1终点为N，从1能到达所有点，所有点也都能到达n，每条边都有一个长度。乐乐从起点出发，走向终点。
到达每一个顶点时，如果有K条离开该点的道路，乐乐可以选择任意一条道路离开该点，并且走向每条路的概率都是 $\frac 1K$ 。
现在乐乐想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入描述:

第一行: 两个整数 N M，代表图中有N个点、M条边。
第二行到第 1+M 行: 每行3个整数 a b c，代表从a到b有一条长度为c的有向边。
。

输出描述:

从起点到终点路径总长度的期望值，四舍五入保留两位小数。

示例1

输入

输出

7.00

算法知识视频讲解

查看答案及解析

Unrepentant

法一：概率DP

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define fo(i,a) for(int i=0;i<a;++i)
#define il inline

const int inf=0x3f3f3f3f,N=100000;

int n,m;
vector<int>e[N];
vector<double>v[N];
double dp[N];

il void read(int &x){
    x=0;char c=getchar(),f=1;
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}

double dfs(int u){
    if(u==n) return 0.0;
    if(dp[u]>-0.5) return dp[u];
    double ans=0;
    for(int i=0,l=e[u].size();i<l;++i){
        ans+=1.0/l*(dfs(e[u][i])+v[u][i]);
    }
    return ans;
}

int main(){
    //freopen("input.txt","r",stdin);
    read(n),read(m);
    int a,b,c;
    go(i,1,m){
        read(a),read(b),read(c);
        e[a].push_back(b);
        v[a].push_back(c);
    }
    mem(dp,0xc2);
    printf("%.2lf",dfs(1));
    return 0;
}

法二：利用期望的线性性

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define fo(i,a) for(int i=0;i<a;++i)
#define il inline

const int inf=0x3f3f3f3f,N=100000;

int n,m;
vector<int>e[N];
vector<double>v[N];
double ans=0.0;

il void read(int &x){
    x=0;char c=getchar(),f=1;
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}

void dfs(int u,double p){
    if(u==n) return;
    for(int i=0,l=e[u].size();i<l;++i){
        ans+=p*1.0/l*v[u][i];
        dfs(e[u][i],p*1.0/l);
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    read(n),read(m);
    int a,b,c;
    go(i,1,m){
        read(a),read(b),read(c);
        e[a].push_back(b);
        v[a].push_back(c);
    }
    dfs(1,1.0);
    printf("%.2lf",ans);
    return 0;
}

发表于 2019-10-30 21:46:44 回复(0)

小元勋

# 拓扑排序逆推：

#include <bits/stdc++.h>
using namespace std;
#define maxn 100050

int st[maxn],top = 0,n,m,head[maxn],sze = 0,du[maxn],du_[maxn];
double f[maxn];
struct edge {
	int v,w,nxt;
}e[maxn<<1];

inline int read_() {
	int x_=0,f_=1;char c_=getchar();
	while(c_<'0'||c_>'9') {if(c_=='-') f_=-1;c_=getchar();}
	while(c_>='0'&&c_<='9') {x_=(x_<<1)+(x_<<3)+c_-'0';c_=getchar();}
	return x_*f_;
}

inline void add_(int u,int v,int w) {
	e[++sze].v = v;
	e[sze].w = w;
	e[sze].nxt = head[u];
	head[u] = sze; 
}

int main() {
	//freopen("a.txt","r",stdin);
	memset(head,-1,sizeof(head));
	n = read_();m = read_();
	int x,y,z;
	for(int i = 1;i <= m;++i) {
		x = read_();y = read_();
		z = read_();add_(y,x,z);
		++du[x];++du_[x];
    }
    st[++top] = n;
    int t = 0,u;
    while( t < top ) {
		u = st[++t];
		if( du_[u] ) f[u] /= du_[u];
    	for(int i = head[u];~i;i = e[i].nxt) {
    		f[e[i].v] += f[u] + e[i].w; 
    		if( --du[e[i].v] == 0 ) st[++top] = e[i].v;
		}
	}
	printf("%.2lf",f[1]);
	return 0;
}

发表于 2019-11-01 21:30:18 回复(0)