ch07 部分题目思路

ch07 部分题目思路

关键边

• 分析
  • 暴力枚举删除每条边即可

struct Node {
    int v, w;   // w: 边权
    bool flag;  // 标记是否删除
};
// 边有边权
vector<Node> G[maxn];
bool vis[maxn];  // 保证每个点只走一次
void dfs(int u) {
    vis[u] = 1;
    for (Node e : G[u]) {
        if (e.flag) continue;  // 此边已删除
        int v = e.v;
        if (!vis[v]) dfs(v);
    }
}
int main() {
    // ...省略输入
    int res = inf;
    for (int u = 1; u <= n; ++u) {  // 枚举起点
        for (Node &e : G[u]) {      // 枚举 u 为起点的每条边
            e.flag = 1;             // 标记删除此边
            // 删除 e 再跑 dfs
            // ...
            if (是关键边) res = min(res, e.w);
            e.flag = 0;  // 撤销删除
        }
    }
    return 0;
}

六度理论

• 分析

  • 记从结点 v 出发能到达的编号最大的结点是 ans[v] 。

  • 如果对于每个结点 v，都从 v 出发进行一次 dfs 或 bfs 遍历计算 ans[v] ，时间复杂度为 O(nm)，会超时。

  • 因为是无向图，“v 能到达的结点”也就是“能到达 v 的结点”，问题转换为求解能到达结点 v 的编号最大的结点。

  • 贪心地按照 从大到小 的顺序，对还未访问过的结点作为起点进行 dfs 或 bfs 遍历搜索，如果从结点 u 出发能到达结点 v，那么 ans[v] 的值为 u。

    • 先从结点 n 出发搜索，对于 n 能到达的每个结点 v，显然能到达 v 的最大结点就是 n，所以 ans[v] = n；
    • 接下来如果结点 n - 1 没被搜索过，那么从 n - 1 出发搜索，以此类推。

  • 访问过的结点不会再次访问，整个图只被遍历一次，时间复杂度 O(n + m)。

六度理论 II

• 分析
  • 与前一题类似，想办法将问题转换为求解能到达结点 v 的编号最大的结点。
  • 对于题目给出的 $u\to v$ 的边，建立反向边，即改为 $v\to u$ 的边。那么 ans[v] 原本要求解从 v 出发能到达的编号最大的结点，改为反向边后转换为求解能到达 v 的编号最大的结点。

「USACO 06DEC」Cow Picnic

• 分析
  • 每个牧场看作一个结点。
  • 使用一个数组 cnt[u] 表示能到牧场 u 的奶牛个数。
  • 分别将 k 头奶牛所在的牧场作为起点进行 dfs 或 bfs。如果能到达结点 u，则 cnt[u] 加一。
  • 最后，对于牧场 u ，若 cnt[u] == k 说明 k 头奶牛都能到达牧场 u。
  • 易错点：有多头奶牛的牧场，不能当做只有一头奶牛处理。
  • 时间复杂度：总共进行 k 次 dfs 或 bfs，O(k(n + m)) 。