「ZJOI2007」最大半连通子图

题目链接:LOJ 10092

原题描述非常直白。

Data Range

$1\leq N\leq 10^5,1\leq M\leq 10^6,X\leq 10^8$。

Solution

博主比较菜,不能严格证明为什么题目给出的最大半联通图就是在原图中找最长链。
题目的本质就是在这个图上找到一条点数最多的链,同时记录方案数。
考虑到题目中可能存在环的情况,考虑环的情况满足所有点都能够到达,所以就缩成一个带权的点,点权为强联通分量内的点数。
特别注意,建立新图的时候不能有两条相同的边,这样会导致重复计数。
我们得到了一张DAG之后就跑一边DP就可以了。
时间复杂度为:$\mathcal O(n)$

Code

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T& x) {
  x = 0; bool flg = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) flg |= ch == '-';
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  flg ? x = -x : 233;
}
const int N = 1e5 + 5;
const int M = 1e6 + 5;
int n, m, MOD, dfc, top, scc;
vector<int> G[N];
vector<int> GN[N];
int dfn[N], low[N], bel[N], stk[N];
pair<int, int> edge[M], edged[N];
bool instk[N];
void tarjan(int u) {
  dfn[u] = low[u] = ++dfc;
  stk[++top] = u; instk[u] = 1;
  for (auto& v : G[u]) {
    if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
    else if (instk[v]) low[u] = min(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    int ver; scc++;
    do { ver = stk[top--]; instk[ver] = 0; bel[ver] = scc; } while (ver != u);
  }
}
void sd() {
  memset(dfn, 0, sizeof dfn);
  scc = top = dfc = 0;
  for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
}
int f[N], g[N], val[N], ind[N];
void DP() {
  memset(f, 0, sizeof f); memset(g, 0, sizeof g);
  static queue<int> q; while (!q.empty()) q.pop();
  for (int i = 1; i <= scc; i++)
    if (!ind[i]) q.push(i), f[i] = val[i], g[i] = 1;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (auto& v : GN[u]) {
      if (val[v] + f[u] > f[v]) f[v] = val[v] + f[u], g[v] = g[u];
      else if (val[v] + f[u] == f[v]) g[v] = (g[v] + g[u]) % MOD;
      if (!--ind[v]) q.push(v);
    }
  }
}
int main() {
  read(n); read(m); read(MOD);
  for (int i = 1; i <= m; i++) {
    int u, v; read(u); read(v);
    G[edge[i].first = u].push_back(edge[i].second = v);
  }
  sd();
  memset(val, 0, sizeof val);
  for (int i = 1; i <= n; i++) val[bel[i]]++;
  int dc = 0;
  for (int i = 1; i <= m; i++) {
    if (bel[edge[i].first] == bel[edge[i].second]) continue;
    edged[++dc] = {bel[edge[i].first], bel[edge[i].second]};
  }
  sort(edged + 1, edged + 1 + dc);
  dc = unique(edged + 1, edged + 1 + dc) - edged - 1;
  for (int i = 1; i <= dc; i++) {
    GN[edged[i].first].push_back(edged[i].second);
    ind[edged[i].second]++;
  }
  DP();
  int ans0 = 0, ans1 = 0;
  for (int i = 1; i <= scc; i++) ans0 = max(ans0, f[i]);
  for (int i = 1; i <= scc; i++) if (f[i] == ans0) ans1 = (ans1 + g[i]) % MOD;
  printf("%d\n%d\n", ans0, ans1);
  return 0;
}
最后修改:2019 年 09 月 22 日 09 : 55 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论