Best Edge Weight

题目描述

You are given a connected weighted graph with $n$ vertices and $m$ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $i$. Let’s determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don’t change the other weights.
You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can’t be two edges with changed weights at the same time.

题意概述

给定一张$n$个点$m$条边的连通无向图,边权均为正数。对于每一条边,询问它的边权至多是多少,使得在其他边权不变的条件下,它在这张图的所有最小生成树中。
数据范围:$2 \le n \le 2 \times 10^5, \; n-1 \le m \le 2 \times 10^5$。

算法分析

题目要求一条边在所有最小生成树中。我们无法求出所有最小生成树,因此先求出其中一棵。这样,图中的边就被分成了两种:一种在这棵最小生成树中,另一种不在这棵最小生成树中。
对于不在这棵最小生成树中的边$(u, v)$,设它的权值为$w$。显然,它和最小生成树上从$u$到$v$的路径构成了一个环。设这条路径上边权的最大值$w_{max}$。如果$w \ge w_{max}$,那么$(u, v)$可能在这张图的一棵最小生成树中,但一定不是所有。因此,可以将$w$设成$w_{max}-1$,因为根据贪心策略,将路径上权值为$w_{max}$的边替换成$(u, v)$,会得到一棵更小的生成树。这种情况很好解决,只要在最小生成树上进行倍增就可以了。
对于在这棵最小生成树中的边$(u, v)$,设它的权值为$w$。假设我们找到了一条不经过这棵最小生成树上的边从$u$到$v$的路径,设这条路径上边权的最小值为$w_{min}$。类似于不在最小生成树的边,如果$w \ge w_{min}$,那么这条边一定不在所有最小生成树中。将它的权值设为$w_{min}-1$,即可满足要求。由于直接求$w_{min}$较为困难,因此可以按边权从小到大枚举不在这棵最小生成树中的边,并用它来更新最小生成树上的一条路径。因为是从小到大枚举,所以最小生成树上的每条边只需要被更新一次,可以用并查集维护。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct line {
  long long u, v, c, id; bool mst;
  bool operator < (const line &a) const { return c < a.c; }
} l[200001];
struct edge {
  long long v, c, id, nxt;
} e[400001];
long long n, m, nume, h[200001], fa[200001], ans[200001];
long long depth[200001], up[200001][20], ma[200001][20], uid[200001];
long long get_fa(long long t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void add_edge(long long u, long long v, long long c, long long id) {
  e[++nume].v = v, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa) {
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa) {
      depth[e[i].v] = depth[t] + 1, up[e[i].v][0] = t;
      ma[e[i].v][0] = e[i].c, uid[e[i].v] = e[i].id, dfs(e[i].v, t);
    }
}
long long get_max(long long u, long long v) {
  long long ret = 0;
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  for (int i = 19; i >= 0; --i)
    if (depth[u] - depth[v] >= (1 << i))
      ret = max(ret, ma[u][i]), u = up[u][i];
  if (u == v) return ret;
  for (int i = 19; i >= 0; --i)
    if (up[u][i] != up[v][i])
      ret = max(ret, max(ma[u][i], ma[v][i])), u = up[u][i], v = up[v][i];
  return max(ret, max(ma[u][0], ma[v][0]));
}
void update(long long u, long long v, long long val) {
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  long long p = u, q = v;
  for (int i = 19; i >= 0; --i)
    if (depth[p] - depth[q] >= (1 << i)) p = up[p][i];
  if (p != q) {
    for (int i = 19; i >= 0; --i)
      if (up[p][i] != up[q][i]) p = up[p][i], q = up[q][i];
    p = up[p][0];
  }
  u = get_fa(u), v = get_fa(v);
  while (depth[u] > depth[p])
    ans[uid[u]] = val - 1, q = get_fa(up[u][0]), fa[u] = q, u = get_fa(u);
  while (depth[v] > depth[p])
    ans[uid[v]] = val - 1, q = get_fa(up[v][0]), fa[v] = q, v = get_fa(v);
}
int main()
{
  cin >> n >> m, memset(ans, -1, sizeof ans);
  if (n == m + 1) {
    for (int i = 1; i <= m; cout << -1 << ' ', ++i); cout << endl; return 0;
  }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; cin >> l[i].u >> l[i].v >> l[i].c, l[i].id = i, ++i);
  sort(l + 1, l + m + 1);
  for (int i = 1; i <= m; ++i) {
    long long u = get_fa(l[i].u), v = get_fa(l[i].v);
    if (u != v) add_edge(l[i].u, l[i].v, l[i].c, l[i].id), fa[u] = v, l[i].mst = true;
  }
  depth[1] = 1, dfs(1, 0);
  for (int i = 1; i < 20; ++i)
    for (int j = 1; j <= n; ++j) {
      up[j][i] = up[up[j][i - 1]][i - 1];
      ma[j][i] = max(ma[j][i - 1], ma[up[j][i - 1]][i - 1]);
    }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; ++i)
    if (!l[i].mst) {
      ans[l[i].id] = get_max(l[i].u, l[i].v) - 1;
      update(l[i].u, l[i].v, l[i].c);
    }
  for (int i = 1; i <= m; cout << ans[i] << ' ', ++i);
  cout << endl;
  return 0;
}

Opening Portals

题目描述

Pavel plays a famous computer game. A player is responsible for a whole country and he can travel there freely, complete quests and earn experience.
This country has $n$ cities connected by $m$ bidirectional roads of different lengths so that it is possible to get from any city to any other one. There are portals in $k$ of these cities. At the beginning of the game all portals are closed. When a player visits a portal city, the portal opens. Strange as it is, one can teleport from an open portal to an open one. The teleportation takes no time and that enables the player to travel quickly between rather remote regions of the country.
At the beginning of the game Pavel is in city number $1$. He wants to open all portals as quickly as possible. How much time will he need for that?

题意概述

给定一张$n$个点$m$条边的无向图,其中$k$个点上有传送器,每条边都有一个权值。初始时所有传送器都处于关闭状态,你在$1$号点。你需要走到所有有传送器的点,将传送器打开。你可以从一个已经打开的传送器直接传送到另一个已经打开的传送器。求经过的所有边的权值和的最小值。
数据范围:$1 \le k \le n \le 10^5, \; 0 \le m \le 10^5$。

算法分析

我们假设所有的点都是传送器。根据最小生成树的性质,这时的最优解就是这张图的最小生成树。显然,如果我们把这张图抽象成只由$k$个有传送器的点构成的“传送图”,这时的最优解也就是“传送图”上的最小生成树。如何构造这张图呢?
计算出每个点到离它最近的传送器的位置$p_i$和距离$d_i$。对于一条权值为$w$的边$(u, v)$,我们将它想象一条权值为$(d_u+w+d_v)$的边$(p_u, p_v)$。这样,这张图上的所有边也就变成了连接$k$个传送器的边。这就可以用Kruskal求最小生成树来解决。这棵最小生成树的边权之和是固定的,因此当$1$号点没有传送器时,可以先走到离它最近的一个有传送器的点。
求$p_i$和$d_i$可以用多源SPFA来完成。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long n, m, k, nume, tot, ans, mi = 1e18;
long long h[100001], p[100001], d[100001], fa[100001], pre[100001];
bool in[100001];
struct edge { long long v, w, nxt; } e[200001];
struct line {
  long long u, v, w;
  bool operator < (const line &a) const {
    return d[u] + w + d[v] < d[a.u] + a.w + d[a.v];
  }
} l[200001];
void add_edge(long long u, long long v, long long w) {
  e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void spfa() {
  queue<long long> que;
  while (!que.empty()) que.pop();
  for (int i = 1; i <= n; ++i)
    if (!d[i]) in[i] = true, que.push(i);
  while (!que.empty()) {
    int u = que.front(); in[u] = false, que.pop();
    for (int i = h[u]; i; i = e[i].nxt)
      if (d[e[i].v] > d[u] + e[i].w) {
        d[e[i].v] = d[u] + e[i].w, pre[e[i].v] = pre[u];
        if (!in[e[i].v]) in[e[i].v] = true, que.push(e[i].v);
      }
  }
}
long long get_fa(long long t) {
  return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    long long u, v, w; cin >> u >> v >> w; add_edge(u, v, w);
  }
  memset(d, 0x1f, sizeof d), d[1] = 0, spfa(); cin >> k;
  for (int i = 1; i <= k; ++i) {
    cin >> p[i]; if (d[p[i]] < mi) mi = d[p[i]];
  }
  ans = mi, memset(d, 0x1f, sizeof d);
  for (int i = 1; i <= n; ++i) fa[i] = i, pre[i] = i;
  for (int i = 1; i <= k; ++i) d[p[i]] = 0; spfa();
  for (int i = 1; i <= n; ++i)
    for (int j = h[i]; j; j = e[j].nxt)
      l[++tot].u = i, l[tot].v = e[j].v, l[tot].w = e[j].w;
  sort(l + 1, l + tot + 1);
  for (int i = 1; i <= tot; ++i) {
    long long u = get_fa(pre[l[i].u]), v = get_fa(pre[l[i].v]);
    if (u != v) fa[u] = v, ans += d[l[i].u] + l[i].w + d[l[i].v];
  }
  cout << ans << endl;
  return 0;
}

Imbalanced Array

题目描述

You are given an array $a$ consisting of $n$ elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array.
For example, the imbalance value of array $[1, 4, 1]$ is $9$, because there are $6$ different subsegments of this array:

  • $[1]$ (from index $1$ to index $1$), imbalance value is $0$;
  • $[1, 4]$ (from index $1$ to index $2$), imbalance value is $3$;
  • $[1, 4, 1]$ (from index $1$ to index $3$), imbalance value is $3$;
  • $[4]$ (from index $2$ to index $2$), imbalance value is $0$;
  • $[4, 1]$ (from index $2$ to index $3$), imbalance value is $3$;
  • $[1]$ (from index $3$ to index $3$), imbalance value is $0$.

You have to determine the imbalance value of the array $a$.

题意概述

给定一个长度为$n$的$a$数组,求
$$\sum_{1 \le i \le j \le n} (max_{i, j}-min_{i, j})$$
其中$max_{i, j}$表示$a_i, a_{i+1}, a_{i+2}, \ldots, a_j$中的最大值,$min_{i, j}$表示$a_i, a_{i+1}, a_{i+2}, \ldots, a_j$中的最小值。
数据范围:$1 \le n \le 10^6, \; 1 \le a_i \le 10^6$。

算法分析1

考虑对于第$i$个数$a_i$,设它作为最大值出现的次数为$mx_i$,作为最小值出现的次数为$mn_i$。那么$ans=\sum_{i=1}^n(mx_i-mn_i)a_i$。接下来的问题就变成了求$mx_i, mn_i$。
对于区间$[l, r]$,我们找出其中的最大(小)值,设为$a_j$,那么$a_j$在$[l, r]$上的$mx_i$($mn_i$)就等于$(j-l+1)(r-j+1)$。可以发现,求解区间$[l, j-1]$和$[j+1, r]$是这个问题的子问题,而且规模更小,可以递归求解。只需在开始时先将数组从大到小(从小到大)排序,令$l=1, r=n$,即可解决原问题。
在求解时可以倒过来思考,即从小到大(从大到小)枚举,并将连续的区间合并,用并查集维护。理论时间复杂度为$O(n\log n)$。

代码1

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct number {
    long long num, id, rec;
} a[1000001];
bool cmp(number a, number b) {return a.num < b.num;}
long long n, fa[1000002], s[1000002], ans;
int get_fa(long long t) {
    return t == fa[t] || fa[t] == 0 ? fa[t] : fa[t] = get_fa(fa[t]);
}
void process(int t) {
    int i, j;
    if (t == 1) i = 1, j = n + 1;
    else i = n, j = 0;
    for (; i != j; i += t) {
        fa[a[i].id] = a[i].id;
        s[a[i].id] = 1;
        long long p = get_fa(a[i].id - 1), q = get_fa(a[i].id + 1);
        a[i].rec = (s[p] + 1) * (s[q] + 1);
        if (s[p]) {
            s[p] += s[get_fa(a[i].id)];
            fa[get_fa(a[i].id)] = p;
        }
        if (s[q]) {
            s[q] += s[get_fa(a[i].id)];
            fa[get_fa(a[i].id)] = q;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].num;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    process(1);
    for (int i = 1; i <= n; ++i) {
        ans += a[i].num * a[i].rec;
    }
    memset(fa, 0, sizeof(fa));
    memset(s, 0, sizeof(s));
    process(-1);
    for (int i = 1; i <= n; ++i) {
        ans -= a[i].num * a[i].rec;
    }
    cout << ans << endl;
    return 0;
}

算法分析2

设$l_i, r_i$分别表示$a_i$作为区间$[l, r]$中的最大(小)值时,$l$的最小值和$r$的最大值。那么对于$a_i$来讲,$mx_i(mn_i)=(i-l_i+1)(r_i-i+1)$。$l_i, r_i$均可以$O(n)$维护(DP或单调栈),从而避免了排序。
注意到有多个数相等时会有重复计算的区间。根据容斥原理,在判断时应一边取等号一边不取等号。

代码2

#include <iostream>
using namespace std;
long long n, a[1000001], l[1000001], r[1000001], ans;
void process(int t) {
    for (int i = 1; i <= n; ++i) {
        l[i] = r[i] = i;
    }
    for (int i = 2; i <= n; ++i) {
        int now = i;
        while (now > 1 && a[i] * t >= a[now - 1] * t) now = l[now - 1];
        l[i] = now;
    }
    for (int i = n - 1; i; --i) {
        int now = i;
        while (now < n && a[i] * t > a[now + 1] * t) now = r[now + 1];
        r[i] = now;
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    process(1);
    for (int i = 1; i <= n; ++i) {
        ans += a[i] * (i - l[i] + 1) * (r[i] - i + 1);
    }
    process(-1);
    for (int i = 1; i <= n; ++i) {
        ans -= a[i] * (i - l[i] + 1) * (r[i] - i + 1);
    }
    cout << ans << endl;
    return 0;
}