Advertisement
Guest User

Untitled

a guest
Aug 4th, 2017
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <memory.h>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <utility>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <cmath>
  11. #include <string>
  12. #include <ctime>
  13.  
  14. using namespace std;
  15.  
  16. #define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(a) (int)((a).size())
  20. typedef long long ll;
  21. typedef long double ld;
  22. typedef pair<int,int> pii;
  23.  
  24. const ld eps = 1e-10;
  25.  
  26. int n, kp, path[510];
  27. vector<int> g[510];
  28. ld a[510][510];
  29. int id[510];
  30. ld p[510], np[510];
  31. bool gg[510][510];
  32.  
  33. int main()
  34. {
  35.   freopen( "in.txt", "r", stdin );
  36.   freopen( "out.txt", "w", stdout );
  37.  
  38.   scanf( "%d", &n );
  39.   scanf( "%d", &kp );
  40.   forn( i, kp ) scanf( "%d", &path[i] );
  41.   forn( i, n )
  42.   {
  43.     int k, x;
  44.     scanf( "%d", &k );
  45.     forn( j, k )
  46.     {
  47.       scanf( "%d", &x );
  48.       g[i].pb( x );
  49.       gg[i][x] = 1;
  50.     }
  51.   }
  52.  
  53.   forn( i, n )
  54.   {
  55.     forn( j, g[i].size() )
  56.       a[ g[i][j] ][i] = 1.0 / g[i].size();
  57.     a[i][i] -= 1.0;
  58.   }
  59.  
  60.   forn( i, n ) a[n-1][i] = 1.0;
  61.   a[n-1][n] = 1.0;
  62. /*  
  63.   forn( i, n )
  64.   {
  65.     forn( j, n+1 ) printf( "%.3f ", (double)a[i][j] );
  66.     printf( "\n" );
  67.   }
  68. */  
  69.   forn( i, n ) id[i] = i;
  70.  
  71.   int N = n+1;
  72.   forn( i, n )
  73.   {
  74.     int j;
  75.     for ( j=i; j<n; j++ )
  76.       if ( fabs( a[ id[j] ][i] ) > eps ) break;
  77.  
  78.     swap( id[i], id[j] );
  79.      
  80.     for ( j=i+1; j<n; j++ )
  81.     {
  82.       ld coeff = -a[ id[j] ][i] / a[ id[i] ][i];
  83.       for ( int q=i; q<N; q++ ) a[ id[j] ][q] += coeff * a[ id[i] ][q];
  84.     }
  85.   }
  86.  
  87.   for ( int i=n-1; i>=0; i-- )
  88.   {
  89.     p[ id[i] ] = a[ id[i] ][n];
  90.     for ( int j=i+1; j<n; j++ ) p[ id[i] ] -= p[ id[j] ] * a[ id[i] ][j];
  91.     p[ id[i] ] /= a[ id[i] ][i];
  92.   }
  93.  
  94. //  forn( i, n ) printf( "%.3f ", (double)p[i] ); printf( "\n" );
  95.   forn( i, kp )
  96.   {
  97.     p[ path[i] ] = 0;
  98.     if ( i < kp-1 )
  99.     {
  100.       forn( j, n ) np[j] = 0;
  101.       forn( j, n )
  102.         forn( q, g[j].size() )
  103.           if ( j != path[i+1] || g[j][q] != path[i] )
  104.             np[ g[j][q] ] += p[j] / g[j].size();
  105.       forn( j, n ) p[j] = np[j];
  106.     }
  107.   }
  108.  
  109.   ld ans = 0;
  110.   forn( j, n ) ans += p[j];
  111.  
  112.   printf( "%.10f\n", double(ans) );
  113.  
  114.   return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement