danihao123's Blog

aji波兰题！（迫真）

啊波兰题真好康（一转）

考虑怎么去除非加油站的影响……对于每两个加油站，取他们的最短路，然后建出来一个图，这个图的MST上的路径的走法就事最优走法。

但这样显然会凉……因为\(s\)肥肠巨大，会T。然后我们考虑多源最短路，并且给每个点标记到它最近的加油站（称为来源）。那么考虑两条加油站间的路径，上面一定有一条边满足边两个端点不一样（证明考虑……如果所有边两边端点的来源都一样，那么所有边的来源会同时事那两个加油站）。

然后一个小问题事，如果一个点有多个来源，只考虑一个会出事吗？这个事不会的。比如说有三个加油站\(a\)、\(b\)、\(c\)，如果说三者到一个点的最短路都一样，那么我们考虑只取\(a\)。如果\(b\)和\(c\)本来能连一条边，但现在因为这个连不了了，那他们还是能同时各和\(a\)连一条长度和原来的那条边长度一样的边，所以事实上没有什么笋丝。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 200005, maxm = 400005;
int first[maxn];
int next[maxm], to[maxm], dist[maxm];
bool dir[maxm];
void add_edge(int u, int v, int w, bool d = true) {
  static int cnt = 0;
  cnt ++; next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = w; dir[cnt] = d;
}
void ins_edge(int u, int v, int w) {
  add_edge(u, v, w); add_edge(v, u, w, false);
}

using ll = long long;
using pii = std::pair<ll, int>;
int n; std::vector<int> V;
ll d[maxn]; int src[maxn];
bool vis[maxn];
void dij() {
  memset(d, 0x1f, sizeof(d));
  std::priority_queue<pii, std::vector<pii>, std::greater<pii> > Q;
  for(auto p : V) {
    d[p] = 0; src[p] = p;
    Q.push(std::make_pair(0LL, p));
  }
  while(!Q.empty()) {
    int u = Q.top().second; Q.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(d[u] + (ll(dist[i])) < d[v]) {
        d[v] = d[u] + (ll(dist[i]));
        src[v] = src[u];
        Q.push(std::make_pair(d[v], v));
      }
    }
  }
}

int p[maxn], rk[maxn];
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return (p[x] = get_fa(p[x]));
  }
}
void link_set(int x, int y) {
  if(rk[x] > rk[y]) std::swap(x, y);
  p[x] = y;
  if(rk[x] == rk[y]) rk[y] ++;
}
void merge_set(int x, int y) {
  x = get_fa(x); y = get_fa(y);
  if(x != y) link_set(x, y);
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
void init_set() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i;
  }
}

struct Edge {
  int u, v; ll w;
  Edge(int a = 0, int b = 0, ll c = 0) {
    u = a; v = b; w = c;
  }
  bool operator <(const Edge &res) const {
    return w < res.w;
  }
};
int m; Edge E[maxm];
int ecnt;
void process() {
  dij(); ecnt = 0;
  for(int i = 1; i <= n; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      int v = to[j];
      if(dir[j] && src[i] != src[v]) {
        E[++ ecnt] = Edge(src[i], src[v], (ll(dist[j])) + d[i] + d[v]);
      }
    }
  }
  std::sort(E + 1, E + 1 + ecnt);
}
bool ans[maxm];
void solve() {
  int q; scanf("%d", &q);
  init_set(); int cur = 0;
  std::vector<std::pair<Edge, int> > Q;
  for(int i = 1; i <= q; i ++) {
    int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
    Q.push_back(std::make_pair(Edge(u, v, w), i));
  }
  std::sort(Q.begin(), Q.end());
  for(auto x : Q) {
    Edge e = x.first;
    while(cur < ecnt && E[cur + 1].w <= e.w) {
      cur ++;
      merge_set(E[cur].u, E[cur].v);
    }
    ans[x.second] = is_same(e.u, e.v);
  }
  for(int i = 1; i <= q; i ++) {
    if(ans[i]) {
      puts("TAK");
    } else {
      puts("NIE");
    }
  }
}

int main() {
  int s; scanf("%d%d%d", &n, &s, &m);
  for(int i = 1; i <= s; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process(); solve();
  return 0;
}

aji波兰题！（直球）

这个题显然就是对那个排列乘上一个置换，然后置换的每一个循环事独立的，于是分别考虑每一个循环。

然后每一个循环有一种显然的构造方法就是从一个点开始，逆着边不停的交换两个点。这样的话有一个点会对答案做\(s - 1\)次贡献（\(s\)为循环大小），其他点都会只做一次循环。显然那个点选权值最小的点事坠吼的。

还有一种构造就是把全局最小值和循环最小值换一下，然后用上面的手段构造，最后再把全局最小值和循环最小值换回来。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 1000005;
int next[maxn];

using ll = long long;
ll m[maxn];
int A[maxn], B[maxn], ma[maxn];
bool vis[maxn];

int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &m[i]);
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]); ma[A[i]] = i;
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]);
    next[ma[B[i]]] = i;
  }
  ll ans = 0LL; ll tv = *std::min_element(m + 1, m + 1 + n);
  for(int i = 1; i <= n; i ++) {
    if(next[i] != i && !vis[i]) {
      int p = i; ll sumv = 0LL, minv = 0x7fffffffLL;
      ll cnt = 0;
      do {
        vis[p] = true; cnt ++;
        sumv += m[A[p]]; minv = std::min(minv, m[A[p]]);
        p = next[p];
      } while(p != i);
      ll delta = sumv + std::min(minv * (cnt - 2LL), minv + tv * (cnt + 1LL));
      ans += delta;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

我从未见过有像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;
}