Advertisement
Fshl0

Untitled

Oct 2nd, 2021
1,124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const int N = 700 + 9;
  7.  
  8. vector <int> adj[N];
  9. int n, m, meh[N], colored[N];
  10. char can[N][N];
  11.  
  12. int Try (int column) {
  13.     if (column > n)
  14.         return 0;
  15.    
  16.     int res = 0;
  17.     for (int i = 1; i <= n; i++) {
  18.         if (colored[i])
  19.             continue;
  20.        
  21.         if (can[i][column] == '0')
  22.             continue;
  23.        
  24.         if (!meh[i])
  25.             continue;
  26.            
  27.         res++;
  28.        
  29.         colored[i] = true;
  30.         for (auto u: adj[i])
  31.             meh[u] = true;
  32.     }
  33.    
  34.     return res + Try (column + 1);
  35. }
  36.  
  37. void solve () {
  38.     cin >> n >> m;
  39.    
  40.     for (int i = 1; i <= m; i++) {
  41.         int u, v;
  42.         cin >> u >> v;
  43.         adj[u].push_back (v);
  44.         adj[v].push_back (u);
  45.     }
  46.    
  47.     for (int i = 1; i <= n; i++)
  48.         for (int j = 1; j <= n; j++)
  49.             cin >> can[i][j];
  50.    
  51.     int res = -1, loly = 0;
  52.    
  53.     for (int firstNode = 1; firstNode <= n; firstNode++) {
  54.         for (int delay = 1; delay <= n; delay++) {
  55.             if (can[firstNode][delay] == '0')
  56.                 continue;
  57.            
  58.             memset (meh, 0, sizeof (meh));
  59.             memset (colored, 0, sizeof (colored));
  60.             meh[firstNode] = colored[firstNode] = true;
  61.             for (auto u: adj[firstNode])
  62.                 meh[u] = true;
  63.                
  64.             int newRes = (1 + Try (delay + 1));
  65.             if (newRes >= res) {
  66.                 res = newRes;
  67.                 loly = delay;
  68.             }
  69.            
  70.             //res = max (res, 1 + Try (delay + 1));
  71.         }  
  72.     }
  73.    
  74.    
  75.     for (int i = 1; i <= n; i++)
  76.         adj[i].clear();
  77.    
  78.     cout << res;
  79.     if (res == -1)
  80.         cout << "\n";
  81.     else {
  82.         cout << " " << loly << "\n";
  83.     }
  84.    
  85.     return;
  86. }
  87.  
  88. int main () {
  89.     int t = 1;
  90.     cin >> t;
  91.    
  92.     while (t--)
  93.         solve ();
  94.        
  95.     return 0;
  96. }
  97.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement