Loading [MathJax]/extensions/tex2jax.js

P4149:「IOI2011」Race 题解

思路

这道题我们直接进行点分治即可。我们需要实现一下的几个操作:

  • FIND-ROOT():找出重心
  • GET-META():更新最小边数答案
  • UPDATE(u, sz):更新边数数组
  • CLEAR():清除边数数组
  • DIVIDE():点分治

我们一段一段来讲。

代码段

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
void predfs(int u, int fa)
{
siz[u] = 1, son[u] = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to, w = edges[i].weight;
if (to == fa || vis[to])
continue;
predfs(to, u);
siz[u] += siz[to], son[u] = max(siz[to], son[u]);
}
son[u] = max(son[u], capacity - siz[u]);
if (son[u] < son[root])
root = u;
}
void predfs(int u, int fa) { siz[u] = 1, son[u] = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to, w = edges[i].weight; if (to == fa || vis[to]) continue; predfs(to, u); siz[u] += siz[to], son[u] = max(siz[to], son[u]); } son[u] = max(son[u], capacity - siz[u]); if (son[u] < son[root]) root = u; }
void predfs(int u, int fa)
{
    siz[u] = 1, son[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to, w = edges[i].weight;
        if (to == fa || vis[to])
            continue;
        predfs(to, u);
        siz[u] += siz[to], son[u] = max(siz[to], son[u]);
    }
    son[u] = max(son[u], capacity - siz[u]);
    if (son[u] < son[root])
        root = u;
}

这一段是找重心的代码,很简单我就不解释了。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
void getMeta(int u, int fa, int cnt, int dist)
{
if (dist > k)
return;
ans = min(ans, sides[k - dist] + cnt);
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (to == fa || vis[to])
continue;
getMeta(to, u, cnt + 1, dist + edges[i].weight);
}
}
void getMeta(int u, int fa, int cnt, int dist) { if (dist > k) return; ans = min(ans, sides[k - dist] + cnt); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (to == fa || vis[to]) continue; getMeta(to, u, cnt + 1, dist + edges[i].weight); } }
void getMeta(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    ans = min(ans, sides[k - dist] + cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        getMeta(to, u, cnt + 1, dist + edges[i].weight);
    }
}

这段比较重要。点分治出来之后就进行子树上的答案统计,答案的计算为\(ans=min\{sides[k – dist] + cnt\}\),其中 sides 数组代表长度为 dist 的最小段数。统计的时候不用担心边重复的问题,因为我们之后 update 操作之后才会让 sides 数组生效。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
void update(int u, int fa, int cnt, int dist)
{
if (dist > k)
return;
sides[dist] = min(sides[dist], cnt);
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (to == fa || vis[to])
continue;
update(to, u, cnt + 1, dist + edges[i].weight);
}
}
void update(int u, int fa, int cnt, int dist) { if (dist > k) return; sides[dist] = min(sides[dist], cnt); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (to == fa || vis[to]) continue; update(to, u, cnt + 1, dist + edges[i].weight); } }
void update(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    sides[dist] = min(sides[dist], cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        update(to, u, cnt + 1, dist + edges[i].weight);
    }
}

用 DFS 进行更新。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
void clear(int u, int fa, int dis)
{
if (dis >= k)
return;
sides[dis] = 1e9;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (vis[to] || fa == to)
continue;
clear(to, u, dis + edges[i].weight);
}
}
void clear(int u, int fa, int dis) { if (dis >= k) return; sides[dis] = 1e9; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to] || fa == to) continue; clear(to, u, dis + edges[i].weight); } }
void clear(int u, int fa, int dis)
{
    if (dis >= k)
        return;
    sides[dis] = 1e9;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to] || fa == to)
            continue;
        clear(to, u, dis + edges[i].weight);
    }
}

设置为极大值来覆盖子树恢复答案。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
void divide(int u, int sz)
{
vis[u] = true, sides[0] = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (vis[to])
continue;
getMeta(to, u, 1, edges[i].weight);
update(to, u, 1, edges[i].weight);
}
clear(u, 0, 0);
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (vis[to])
continue;
son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]);
root = 0;
predfs(to, 0);
divide(root, capacity);
}
}
void divide(int u, int sz) { vis[u] = true, sides[0] = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to]) continue; getMeta(to, u, 1, edges[i].weight); update(to, u, 1, edges[i].weight); } clear(u, 0, 0); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to]) continue; son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]); root = 0; predfs(to, 0); divide(root, capacity); } }
void divide(int u, int sz)
{
    vis[u] = true, sides[0] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        getMeta(to, u, 1, edges[i].weight);
        update(to, u, 1, edges[i].weight);
    }
    clear(u, 0, 0);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]);
        root = 0;
        predfs(to, 0);
        divide(root, capacity);
    }
}

点分治是在重心上运行的。在重心上更新子树的信息,然后进行换根保证正确性。

总代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// P4149.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200200;
struct edge
{
int to, nxt, weight;
} edges[MAX_N << 1];
int head[MAX_N], n, k, current, tmpx, tmpy, tmpz, siz[MAX_N], capacity;
int ans = 1e9, sides[1002000], son[MAX_N], root;
bool vis[MAX_N];
inline int read()
{
int re = 0, flag = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
flag = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
re = (re << 1) + (re << 3) + ch - '0', ch = getchar();
return re * flag;
}
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
void predfs(int u, int fa)
{
siz[u] = 1, son[u] = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to, w = edges[i].weight;
if (to == fa || vis[to])
continue;
predfs(to, u);
siz[u] += siz[to], son[u] = max(siz[to], son[u]);
}
son[u] = max(son[u], capacity - siz[u]);
if (son[u] < son[root])
root = u;
}
void getMeta(int u, int fa, int cnt, int dist)
{
if (dist > k)
return;
ans = min(ans, sides[k - dist] + cnt);
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (to == fa || vis[to])
continue;
getMeta(to, u, cnt + 1, dist + edges[i].weight);
}
}
void update(int u, int fa, int cnt, int dist)
{
if (dist > k)
return;
sides[dist] = min(sides[dist], cnt);
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (to == fa || vis[to])
continue;
update(to, u, cnt + 1, dist + edges[i].weight);
}
}
void clear(int u, int fa, int dis)
{
if (dis >= k)
return;
sides[dis] = 1e9;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (vis[to] || fa == to)
continue;
clear(to, u, dis + edges[i].weight);
}
}
void divide(int u, int sz)
{
vis[u] = true, sides[0] = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (vis[to])
continue;
getMeta(to, u, 1, edges[i].weight);
update(to, u, 1, edges[i].weight);
}
clear(u, 0, 0);
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (vis[to])
continue;
son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]);
root = 0;
predfs(to, 0);
divide(root, capacity);
}
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &k);
for (int i = 0; i < n - 1; i++)
{
scanf("%d%d%d", &tmpx, &tmpy, &tmpz);
addpath(tmpx + 1, tmpy + 1, tmpz), addpath(tmpy + 1, tmpx + 1, tmpz);
}
capacity = n;
son[0] = n, root = 0;
for (int i = 0; i <= k; i++)
sides[i] = 1e9;
predfs(1, 0);
divide(root, n);
if (ans != 1e9)
printf("%d", ans);
else
printf("-1");
return 0;
}
// P4149.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 200200; struct edge { int to, nxt, weight; } edges[MAX_N << 1]; int head[MAX_N], n, k, current, tmpx, tmpy, tmpz, siz[MAX_N], capacity; int ans = 1e9, sides[1002000], son[MAX_N], root; bool vis[MAX_N]; inline int read() { int re = 0, flag = 1; char ch = getchar(); while (ch > '9' || ch < '0') { if (ch == '-') flag = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') re = (re << 1) + (re << 3) + ch - '0', ch = getchar(); return re * flag; } void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].nxt = head[src]; edges[current].weight = weight, head[src] = current++; } void predfs(int u, int fa) { siz[u] = 1, son[u] = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to, w = edges[i].weight; if (to == fa || vis[to]) continue; predfs(to, u); siz[u] += siz[to], son[u] = max(siz[to], son[u]); } son[u] = max(son[u], capacity - siz[u]); if (son[u] < son[root]) root = u; } void getMeta(int u, int fa, int cnt, int dist) { if (dist > k) return; ans = min(ans, sides[k - dist] + cnt); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (to == fa || vis[to]) continue; getMeta(to, u, cnt + 1, dist + edges[i].weight); } } void update(int u, int fa, int cnt, int dist) { if (dist > k) return; sides[dist] = min(sides[dist], cnt); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (to == fa || vis[to]) continue; update(to, u, cnt + 1, dist + edges[i].weight); } } void clear(int u, int fa, int dis) { if (dis >= k) return; sides[dis] = 1e9; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to] || fa == to) continue; clear(to, u, dis + edges[i].weight); } } void divide(int u, int sz) { vis[u] = true, sides[0] = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to]) continue; getMeta(to, u, 1, edges[i].weight); update(to, u, 1, edges[i].weight); } clear(u, 0, 0); for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (vis[to]) continue; son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]); root = 0; predfs(to, 0); divide(root, capacity); } } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &k); for (int i = 0; i < n - 1; i++) { scanf("%d%d%d", &tmpx, &tmpy, &tmpz); addpath(tmpx + 1, tmpy + 1, tmpz), addpath(tmpy + 1, tmpx + 1, tmpz); } capacity = n; son[0] = n, root = 0; for (int i = 0; i <= k; i++) sides[i] = 1e9; predfs(1, 0); divide(root, n); if (ans != 1e9) printf("%d", ans); else printf("-1"); return 0; }
// P4149.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200200;
struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 1];
int head[MAX_N], n, k, current, tmpx, tmpy, tmpz, siz[MAX_N], capacity;
int ans = 1e9, sides[1002000], son[MAX_N], root;
bool vis[MAX_N];
inline int read()
{
    int re = 0, flag = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            flag = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        re = (re << 1) + (re << 3) + ch - '0', ch = getchar();
    return re * flag;
}
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}
void predfs(int u, int fa)
{
    siz[u] = 1, son[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to, w = edges[i].weight;
        if (to == fa || vis[to])
            continue;
        predfs(to, u);
        siz[u] += siz[to], son[u] = max(siz[to], son[u]);
    }
    son[u] = max(son[u], capacity - siz[u]);
    if (son[u] < son[root])
        root = u;
}
void getMeta(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    ans = min(ans, sides[k - dist] + cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        getMeta(to, u, cnt + 1, dist + edges[i].weight);
    }
}
void update(int u, int fa, int cnt, int dist)
{
    if (dist > k)
        return;
    sides[dist] = min(sides[dist], cnt);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (to == fa || vis[to])
            continue;
        update(to, u, cnt + 1, dist + edges[i].weight);
    }
}
void clear(int u, int fa, int dis)
{
    if (dis >= k)
        return;
    sides[dis] = 1e9;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to] || fa == to)
            continue;
        clear(to, u, dis + edges[i].weight);
    }
}
void divide(int u, int sz)
{
    vis[u] = true, sides[0] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        getMeta(to, u, 1, edges[i].weight);
        update(to, u, 1, edges[i].weight);
    }
    clear(u, 0, 0);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (vis[to])
            continue;
        son[0] = capacity = (siz[to] > siz[u]) ? (sz - siz[u]) : (siz[to]);
        root = 0;
        predfs(to, 0);
        divide(root, capacity);
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz);
        addpath(tmpx + 1, tmpy + 1, tmpz), addpath(tmpy + 1, tmpx + 1, tmpz);
    }
    capacity = n;
    son[0] = n, root = 0;
    for (int i = 0; i <= k; i++)
        sides[i] = 1e9;
    predfs(1, 0);
    divide(root, n);
    if (ans != 1e9)
        printf("%d", ans);
    else
        printf("-1");
    return 0;
}

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *