Description

有一张带点权有向图，你要在其中修建若干个检查站，使得对于每一个点 \(p\) ，都有 \(\geq 1\) 个检查站，满足：

存在一条从这个检查站出发到点 \(p\) 的路径；
存在一条从点 \(p\) 出发到这个检查站的路径。

求出修建检查站的点权和的最小值，以及当点权和有最小值时的修建方案数。

Solution

对于每个强连通分量，只需要修建 \(1\) 个检查站。

所以可以考虑缩点，这样最小点权和就是每个强连通分量中最小点权之和。

至于修建方案数，可以考虑乘法原理。总方案数等于每个强连通分量中方案数的乘积。

而每个强连通分量的方案数就是强连通分量中点权等于最小点权的点的个数。

然后这道题目就愉快地做完了。

using std::vector;

struct Edge {

  ll to, nex;

} e[1000010];

ll dfn[1000010], low[1000010], dfncnt;

ll s[1000010], in_stack[1000010], tp;

ll belong[1000010], sc, sz[1000010];

ll head[1000010], cnt;

ll ans = 1, ans2;

ll val[1000010];

vector<ll> scc[1000010];

void add(ll u, ll v) {

  e[++cnt].to = v;

  e[cnt].nex = head[u];

  head[u] = cnt;

}

void tarjan(ll u) {

  low[u] = dfn[u] = ++dfncnt;

  s[++tp] = u, in_stack[u] = 1;

  for(ll i = head[u]; i; i = e[i].nex) {

    ll v = e[i].to;

    if(!dfn[v]) {

      tarjan(v);

      low[u] = min(low[u], low[v]);

    } else if(in_stack[v]) {

      low[u] = min(low[u], dfn[v]);

    }

  }

  if(dfn[u] == low[u]) {

    ll it = 0;

    ++sc;

    while(s[tp] != u) {

      belong[s[tp]] = sc;

      sz[sc]++;

      in_stack[s[tp]] = 0;

      scc[sc].push_back(val[s[tp]]);

      --tp;

    }

    belong[s[tp]] = sc;

    sz[sc]++;

    in_stack[s[tp]] = 0;

    scc[sc].push_back(val[s[tp]]);

    --tp;

    std::sort(scc[sc].begin(), scc[sc].end());

    rep(i, 0, sz[sc] - 1) if(scc[sc][i] == scc[sc][0]) ++it;

    ans = ans * it % 1000000007ll;

    ans2 += scc[sc][0];

  }

}

int main() {

  ll n, m;

  read(n);

  rep(i, 1, n) read(val[i]);

  read(m);

  rep(i, 1, m) {

    ll x, y;

    read(x), read(y);

    add(x, y);

  }

  rep(i, 1, n) if(!dfn[i]) tarjan(i);

  print(ans2), putchar(' '), print(ans);

  return 0;

}

巴特西

CF427C题解

Description

Solution

最新文章

热门文章