Submission #42101507

---

Source Code Expand

// LUOGU_RID: 112375714
#include<bits/stdc++.h>
using namespace std;
const int maxn = 605;
const int maxm = 605 * 605 / 2;
double dp[maxn],f[maxn];
int n,m,out[maxn];
struct edge
{
	int to,nxt;
}e[maxm << 1];
int head[maxn],tot,maxx;
double ans;
void add_edge(int u,int v)
{
	e[++tot].nxt = head[u];
	head[u] = tot;
	e[tot].to = v;
}
void solve(int u)
{
	maxx = 0;
	out[u]--;
	for(int i = head[u];i;i = e[i].nxt)
	{
		int v = e[i].to;
		if(f[v] > f[maxx])
		{
			maxx = v;
		}
	}
	memset(dp,0,sizeof(dp));
	for(int x = n;x;x--)
    {
        for(int i = head[x];i;i = e[i].nxt)
        {
            int v = e[i].to;
            if(u == x && v == maxx)
                continue;
            dp[x] += (dp[v] + 1) / out[x];
        }
    }
	out[u]++;
	if(dp[1])
	{
		ans = min(ans,dp[1]);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		cin >> u >> v;
		add_edge(u,v);
		out[u]++;//计算出度
	}
	for(int u = n - 1;u;u--)
    {
        for(int i = head[u];i;i = e[i].nxt)
        {
            int v = e[i].to;
            f[u] += (f[v] + 1) / out[u];//初始的期望值
        }
    }
	ans = f[1];
	for(int i = 1;i < n;i++)
	{
		if(out[i] == 1)
		{
			continue;
		}
		solve(i);
	}
	printf("%.10lf",ans);
	return 0;
}

Submission Info

Judge Result