我从未见过有像SZKOpuł这样迷的OJ……

很好玩的一道题qwq

首先多源最短路太不好处理，我们搞一个超级源一个超级汇，分别和所有点连边。然后转成求超级源和超级汇的最长路。

我们不妨将这张图拓扑排序。然后我们思考对于拓扑排序得到的序列\(A\)，如果我们删除\(A_i\)的话，哪些路径不会收到影响？如果说有一个路径有一条边\((u, v)\)，满足\(u\)和\(v\)在拓扑排序中分别位于\(A_i\)的两侧，那么这条路径不会受到影响。

反过来考虑每条边\((u, v)\)，过这条边最优的路径一定是从源到\(u\)的最长路加上1再加上从\(v\)到汇的最长路（用两遍DP就能搞出来），他能影响的点在拓扑排序中显然事一段区间。

然后问题变成区间取max了，然后不需要在线，所以随便做了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int maxn = 500005;
const int maxm = 750005;
std::vector<int> G[maxn], RG[maxn];
int inv[maxn], outv[maxn];
void add_edge(int u, int v) {
  inv[v] ++; outv[u] ++;
  G[u].push_back(v);
  RG[v].push_back(u);
}

int T[maxn], ma[maxn];
void toposort() {
  std::queue<int> Q; Q.push(0);
  int num = 0;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    T[++ num] = u; ma[u] = num;
    for(auto v : G[u]) {
      inv[v] --;
      if(inv[v] == 0) Q.push(v);
    }
  }
}

int n, m;
int f[maxn], g[maxn];
int dp1(int x) {
  if(x == n + 1) return 0;
  if(f[x] != -1) return f[x];
  f[x] = 0;
  for(auto v : G[x]) {
    f[x] = std::max(f[x], dp1(v) + 1);
  }
  return f[x];
}
int dp2(int x) {
  if(x == 0) return 0;
  if(g[x] != -1) return g[x];
  g[x] = 0;
  for(auto v : RG[x]) {
    g[x] = std::max(g[x], dp2(v) + 1);
  }
  return g[x];
}

struct Interval {
  int l, r, v;
  bool operator <(const Interval &res) const {
    return v < res.v;
  }
};
int E[maxm][2]; std::vector<Interval> I;
void pro_I() {
  memset(f, -1, sizeof(f));
  memset(g, -1, sizeof(g));
  for(int u = 0; u <= n + 1; u ++) {
    for(auto v : G[u]) {
      int l = ma[u], r = ma[v];
      l ++; r --;
      if(l <= r) {
        Interval seg;
        seg.l = l; seg.r = r;
        seg.v = dp2(u) + dp1(v) + 1;
        I.push_back(seg);
      }
    }
  }
  std::sort(I.begin(), I.end());
}

const int maxno = maxn << 2;
int setv[maxno];
void pushdown(int o) {
  if(setv[o] != -1) {
    int lc = o << 1, rc = o << 1 | 1;
    setv[lc] = setv[o]; setv[rc] = setv[o];
    setv[o] = -1;
  }
}
int ql, qr, v;
void modify(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    setv[o] = v;
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) modify(o << 1, L, M);
    if(qr > M) modify(o << 1 | 1, M + 1, R);
  }
}
int ans[maxn];
void dfs(int o, int L, int R) {
  if(L == R) {
    ans[L] = setv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    dfs(o << 1, L, M);
    dfs(o << 1 | 1, M + 1, R);
  }
}

int main() {
  memset(setv, -1, sizeof(setv));
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &E[i][0], &E[i][1]);
    add_edge(E[i][0], E[i][1]);
  }
  for(int i = 1; i <= n; i ++) {
    if(true) {
      add_edge(0, i);
    }
  }
  for(int i = 1; i <= n; i ++) {
    if(true) {
      add_edge(i, n + 1);
    }
  }
  toposort(); pro_I();
  for(auto &seg : I) {
    ql = seg.l, qr = seg.r, v = seg.v;
#ifdef LOCAL
    printf("(%d, %d) -> %d\n", ql, qr, v);
#endif
    modify(1, 1, n + 2);
  }
  dfs(1, 1, n + 2);
  int cho = 1, ret = 0x7fffffff;
  for(int i = 2; i <= n + 1; i ++) {
    if(ans[i] < ret) {
      cho = T[i]; ret = ans[i];
    }
  }
  printf("%d %d\n", cho, ret - 2);
  return 0;
}

• 相关文章
• 全局相关文章