icon

2018-11-19

USACO Network of Schools

link

  • A问最少从几个点出发就能reach整张图。
  • B问最少加几条边就能让任意两点之间互相连接。

想到用强联通分量就比较好做了。

A问只需要先拓扑排序,然后逆序DFS就行,因为这样可以保证用的点最少。

B问我这里用了贪心:每次找出所有scc,然后连接连接第一和末尾scc中的任意两个点;如此往复,直到scc数量变为1。

这样做的原因是:拓扑排序排在最后面的scc肯定(必须)是要有新的边连出来的,那么不如直接连到最前面好了。

/*
ID: mwx36mw2
TASK: schlnet
LANG: C++11
*/
// Author: Wenxing Mei
//   Date: 2018-11-16 16:52
#include <bits/stdc++.h>
#ifdef LOCAL
#include <unistd.h>
#endif
using namespace std;
#define rep(i, solve_a, solve_b) for (int i = (int)solve_a; i < (int)solve_b; ++i)
#define per(i, solve_b, solve_a) for (int i = (int)solve_b - 1; i >= (int)solve_a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE

vi topsort(vvi &adj) {
  int n = adj.size();
  vi vis(n, 0);
  vi re;
  function<void(int)> dfs = [&](int u) {
    vis[u] = 1;
    repv(v, adj[u]) {
      if (!vis[v]) dfs(v);
    }
    re.eb(u);
  };
  rep(i, 0, n) {
    if (!vis[i]) dfs(i);
  }
  return re;
}

void solve_a(vvi &adj) {
  vi seq = topsort(adj);
  int n = adj.size();
  vi vis(n, 0);
  function<void(int)> dfs = [&](int u) {
    vis[u] = 1;
    repv(v, adj[u]) {
      if (!vis[v]) dfs(v);
    }
  };
  int cnt = 0;
  per(i, n, 0) {
    if (!vis[seq[i]]) {
      ++cnt;
      dfs(seq[i]);
    }
  }
  cout << cnt << '\n';
}

vvi scc(vvi &adj, vvi &rev) {
  int n = adj.size();
  vi seq = topsort(rev);
  vvi ans;
  vi cur, vis(n, 0);
  function<void(int)> dfs = [&](int u) {
    vis[u] = 1;
    repv(v, adj[u]) {
      if (!vis[v]) dfs(v);
    }
    cur.eb(u);
  };
  per(i, n, 0) {
    if (!vis[seq[i]]) {
      cur.clear();
      dfs(seq[i]);
      ans.eb(cur);
    }
  }
  return ans;
}

void solve_b(vvi &adj, vvi &rev) {
  int cnt = 0;
  while (1) {
    vvi sc = scc(adj, rev);
    if (sc.size() == 1) break;

    int u = sc.front().front();
    int v = sc.back().back();
    adj[u].eb(v);
    rev[v].eb(u);
    ++cnt;
  }
  cout << cnt << '\n';
}

int main() {
#ifndef LOCAL
  freopen("schlnet.in", "r", stdin);
  freopen("schlnet.out", "w", stdout);
  ios_base::sync_with_stdio(0), cin.tie(0);
#endif
  int n;
  cin >> n;
  vvi adj(n), rev(n);
  rep(i, 0, n) {
    int x;
    while (cin >> x, x) {
      adj[i].eb(x - 1);
      rev[x - 1].eb(i);
    }
  }

  solve_a(adj);
  solve_b(adj, rev);

  return 0;
}
/*
USER: wenxing mei [mwx36mw2]
TASK: schlnet
LANG: C++11

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.004 secs, 1288 KB]
   Test 2: TEST OK [0.000 secs, 1296 KB]
   Test 3: TEST OK [0.004 secs, 1284 KB]
   Test 4: TEST OK [0.000 secs, 1320 KB]
   Test 5: TEST OK [0.000 secs, 1336 KB]
   Test 6: TEST OK [0.004 secs, 1352 KB]
   Test 7: TEST OK [0.004 secs, 1288 KB]
   Test 8: TEST OK [0.004 secs, 1336 KB]
   Test 9: TEST OK [0.000 secs, 1356 KB]
   Test 10: TEST OK [0.004 secs, 1352 KB]
   Test 11: TEST OK [0.004 secs, 1320 KB]

All tests OK.
Your program ('schlnet') produced all correct answers!  This is your
submission #6 for this problem.  Congratulations!
*/
comments powered by Disqus

search See also