fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int n, m;
  8.     if(!(cin >> n >> m)) return 0;
  9.     vector<pair<int,int>> edges(m);
  10.     vector<vector<int>> adj(n+1);
  11.     vector<int> deg(n+1,0);
  12.     for(int i=0;i<m;i++){
  13.         int u,v; cin >> u >> v;
  14.         edges[i] = {u,v};
  15.         adj[u].push_back(v);
  16.         adj[v].push_back(u);
  17.         deg[u]++; deg[v]++;
  18.     }
  19.  
  20.     // Build linear system for t[1..n-1] (exclude n). We'll index rows for vertices 1..n-1.
  21.     int N = n-1; // number of unknowns (if n==1 impossible by constraints)
  22.     vector<vector<double>> A(N, vector<double>(N+1, 0.0)); // augmented matrix
  23.  
  24.     auto idx = [&](int v)->int{ // map vertex v (1..n-1) to row index 0..N-1
  25.         return v-1;
  26.     };
  27.  
  28.     for(int v=1; v<=n-1; ++v){
  29.         int r = idx(v);
  30.         A[r][r] = 1.0;
  31.         // subtract contributions: for each u (neighbour) with u != n, coefficient of t[u] is -P(u->v) = -1/deg(u) if edge(u,v)
  32.         for(int u=1; u<=n; ++u){
  33.             // we need term for neighbors u that have edge u-v; faster to iterate adjacency of v
  34.             // but we need P(u->v) so iterate neighbors u of v? we will instead loop adj[v]
  35.         }
  36.     }
  37.     // Fill properly by iterating u for each neighbor relation:
  38.     for(int u=1; u<=n; ++u){
  39.         for(int v_nei : adj[u]){
  40.             // there is edge u -> v_nei, add -1/deg(u) to equation for v_nei (if v_nei != n)
  41.             if(v_nei == n) continue;
  42.             if(u == n) continue; // if u==n, P(n->*) doesn't matter because we never depart from n (absorbing)
  43.             int row = idx(v_nei);
  44.             int col = idx(u);
  45.             A[row][col] -= 1.0 / deg[u];
  46.         }
  47.     }
  48.     // RHS b: b[v] = 1 if v==1 else 0
  49.     for(int v=1; v<=n-1; ++v){
  50.         int r = idx(v);
  51.         A[r][N] = (v==1) ? 1.0 : 0.0;
  52.     }
  53.  
  54.     // Solve A * t = b by Gaussian elimination (partial pivot)
  55.     for(int col=0, row=0; col<N && row<N; ++col, ++row){
  56.         // find pivot
  57.         int piv = row;
  58.         for(int i=row;i<N;++i){
  59.             if(fabs(A[i][col]) > fabs(A[piv][col])) piv = i;
  60.         }
  61.         if(fabs(A[piv][col]) < 1e-15){
  62.             // column is (nearly) zero, skip (shouldn't happen in connected graph)
  63.             --row;
  64.             continue;
  65.         }
  66.         if(piv != row) swap(A[piv], A[row]);
  67.         // normalize and eliminate
  68.         double pivot = A[row][col];
  69.         for(int j=col;j<=N;j++) A[row][j] /= pivot;
  70.         for(int i=0;i<N;++i){
  71.             if(i==row) continue;
  72.             double factor = A[i][col];
  73.             if(fabs(factor) < 1e-18) continue;
  74.             for(int j=col;j<=N;j++){
  75.                 A[i][j] -= factor * A[row][j];
  76.             }
  77.         }
  78.     }
  79.  
  80.     vector<double> t(n+1, 0.0);
  81.     for(int v=1; v<=n-1; ++v){
  82.         int r = idx(v);
  83.         t[v] = A[r][N];
  84.     }
  85.     t[n] = 0.0;
  86.  
  87.     // compute w_e for each edge
  88.     vector<double> w(m);
  89.     for(int i=0;i<m;i++){
  90.         int u = edges[i].first;
  91.         int v = edges[i].second;
  92.         double wu = (deg[u] > 0) ? t[u] / deg[u] : 0.0;
  93.         double wv = (deg[v] > 0) ? t[v] / deg[v] : 0.0;
  94.         w[i] = wu + wv;
  95.     }
  96.  
  97.     // sort descending
  98.     sort(w.begin(), w.end(), greater<double>());
  99.  
  100.     // compute answer = sum_{i=1..m} i * w[i-1]
  101.     long double ans = 0.0L;
  102.     for(int i=0;i<m;i++){
  103.         ans += (long double)(i+1) * (long double)w[i];
  104.     }
  105.  
  106.     cout.setf(std::ios::fixed); cout<<setprecision(3)<<(double)ans<<"\n";
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
3 3
2 3
1 2
1 3
stdout
copy 
3.333
https://ideone.com/MIdY6D
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!