Advertisement
ivnikkk

Untitled

Dec 19th, 2022
697
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(mask) mask.begin(), mask.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef pair<int, int> pii;
  9. typedef long double ld;
  10.  
  11. int gr[41][41];
  12. int deg[41], mask[41];
  13. int depth, n;
  14. void dfs(int j, int c){
  15.     if (c + n - j + 1 <= depth)
  16.         return;
  17.     bool fl;
  18.     if (j == n + 1){
  19.         if (c > depth) {
  20.             depth = c;
  21.         }
  22.         return;
  23.     }
  24.     fl = true;
  25.     if (deg[j] <= depth - 1) {
  26.         fl = false;
  27.     }
  28.     else {
  29.         for (int i = 1; i <= c; i++) {
  30.             if (gr[mask[i]][j] == 0) {
  31.                 fl = false;
  32.                 break;
  33.             }
  34.         }
  35.     }
  36.     if (fl) {
  37.         mask[c + 1] = j;
  38.         dfs(j + 1, c + 1);
  39.     }
  40.     dfs(j + 1, c);
  41. }
  42. signed main() {
  43. #ifdef _DEBUG
  44.     freopen("input.txt", "r", stdin);
  45.     freopen("output.txt", "w", stdout);
  46. #endif
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(nullptr);
  49.     cout.tie(nullptr);
  50.     cout << fixed << setprecision(8);
  51.     int k;
  52.     ld ans;
  53.     cin >> n >> k;
  54.     for (int i = 0; i < 41; i++) {
  55.         deg[i] = 0;
  56.         mask[i] = 0;
  57.     }
  58.     for (int i = 1; i <= n; i++) {
  59.         for (int j = 1; j <= n; j++) {
  60.             cin >> gr[i][j];
  61.             if (gr[i][j] == 1) {
  62.                 deg[i]++;
  63.             }
  64.         }
  65.     }
  66.     depth = 1;
  67.     dfs(1, 0);
  68.     cout << (ld)((depth - 1) * k * k) / (ld)(2 * depth) << '\n';
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement