SHARE
TWEET

Penguin-Avia

Giatro May 25th, 2020 2,397 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. typedef unsigned long long int ull;
  6. typedef long double lld;
  7. typedef pair<ll, ll> pll;
  8. typedef pair<int, int> pii;
  9. typedef vector<ll> vl;
  10. typedef vector<int> vi;
  11. typedef vector<pii> vii;
  12. typedef vector<pll> vll;
  13.  
  14. #define fastio                        \
  15.     ios_base::sync_with_stdio(false); \
  16.     cin.tie(NULL);                    \
  17.     cout.tie(NULL)
  18.  
  19. #define fr(i, n) for (ll i = 0; i < n; i++)
  20. #define frr(i, n) for (ll i = 1; i <= n; i++)
  21. #define frit(it, c) for (auto it = c.begin(); it != c.end(); it++)
  22.  
  23. #define sortvector(v) sort(v.begin(), v.end())
  24. #define sortvectorby(v, f) sort(v.begin(), v.end(), f)
  25.  
  26. #define pb push_back
  27. #define mk make_pair
  28. #define f first
  29. #define s second
  30.  
  31. #define debug(x) cout << #x << " = " << x << endl
  32.  
  33. const int INF = 0x3f3f3f3f;
  34. const ll LINF = 0x3f3f3f3f3f3f3f;
  35. const ll M = 1000000007;
  36. // ===================================================== //
  37.  
  38. const int N = 112;
  39. int n, a, d;
  40. char adj[N][N];
  41. int uf[N], w[N];
  42.  
  43. int find(int u) { return (uf[u] == u ? u : uf[u] = find(uf[u])); }
  44.  
  45. void join(int u, int v) {
  46.     u = find(u);
  47.     v = find(v);
  48.     if (w[u] < w[v]) swap(u, v);
  49.     w[u] += w[v];
  50.     uf[v] = u;
  51. }
  52.  
  53. void bfs(int s, int comp) {
  54.     for (int i = 0; i < n; i++) {
  55.         if (adj[s][i] == '1' && uf[i] != comp) {
  56.             uf[i] = comp;
  57.             adj[s][i] = adj[i][s] = '2';
  58.             bfs(i, comp);
  59.         }
  60.     }
  61. }
  62.  
  63. void allbfs() {
  64.     int tot = 0;
  65.     fr(i, n) {
  66.         uf[i] = -1;
  67.         w[i] = 1;
  68.     }
  69.  
  70.     fr(i, n) {
  71.         if (uf[i] == -1) {
  72.             uf[i] = i;
  73.             bfs(i, i);
  74.         }
  75.     }
  76.  
  77.     fr(i, n) {
  78.         if (find(0) != find(i)) {
  79.             join(0, i);
  80.             adj[0][i] = adj[i][0] = 'a';
  81.             tot += a;
  82.         }
  83.     }
  84.  
  85.     fr(i, n) fr(j, n) {
  86.         if (adj[i][j] == '2') adj[i][j] = adj[j][i] = '0';
  87.  
  88.         if (adj[i][j] == '1') {
  89.             adj[i][j] = adj[j][i] = 'd';
  90.             tot += d;
  91.         }
  92.     }
  93.  
  94.     cout << tot << endl;
  95. }
  96.  
  97. int main(int argc, char const *argv[]) {
  98.     fastio;
  99.     cin >> n;
  100.     cin >> d >> a;
  101.  
  102.     fr(i, n) fr(j, n) cin >> adj[i][j];
  103.  
  104.     allbfs();
  105.  
  106.     fr(i, n) {
  107.         fr(j, n) cout << adj[i][j];
  108.         cout << endl;
  109.     }
  110.  
  111.     return 0;
  112. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top