Submission #8237027

---

Source Code Expand

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst) : src(src), dst(dst) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void edges_to_graph(Graph &graph, const Edges &edges, const int vertices, const bool directed = true) {
  graph.resize(vertices);
  for (const auto &e : edges) graph[e.src].emplace_back(e);
  if (!directed) for (const auto &e : edges) graph[e.dst].emplace_back(Edge(e.dst, e.src, e.weight));
}

int main(void) {
  int n, m;
  cin >> n >> m;
  Graph graph;
  Edges edges(m);
  rep (i, m) {
    int s, t;
    cin >> s >> t;
    edges[i] = {--s, --t};
  }
  edges_to_graph(graph, edges, n);
  vector<double> svp(n), nv(n);
  svp[0] = 1;
  rep (i, n - 1) {
    double p = svp[i] / graph[i].size();
    allrep (e, graph[i]) svp[e.dst] += p;
  }
  rrep (i, n - 1) {
    double sum = 0;
    allrep (e, graph[i]) sum += nv[e.dst];
    nv[i] = sum / graph[i].size() + 1;
  }
  double maxdec = 0;
  rep (i, n - 1) {
    const int en = graph[i].size();
    if (en == 1) continue;
    double maxi = -1;
    allrep (e, graph[i]) maxi = max(maxi, nv[e.dst]);
    double newnv = ((nv[i] - 1) * en - maxi) / (en - 1) + 1;
    maxdec = max(maxdec, (nv[i] - newnv) * svp[i]);
  }
  cout << nv[0] - maxdec << endl;
  return 0;
}

Submission Info

Judge Result