USACO历年黄金组真题解析 | 2006年1月

欢迎大家订阅我的专栏：算法通关攻略：高效刷题，告别无效练习！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年黄金组真题解析 | 汇总

P2860 Redundant Paths

【题目来源】

洛谷：[P2860 USACO06JAN] Redundant Paths G - 洛谷

【题目描述】

为了从 \(F(1\le F\le 5,000)\) 个牧场（编号为 \(1\) 到 \(F\)）中的一个到达另一个牧场，贝西和其他牛群被迫经过腐烂苹果树附近。奶牛们厌倦了经常被迫走特定的路径，想要修建一些新路径，以便在任意一对牧场之间总是有至少两条独立的路线可供选择。目前在每对牧场之间至少有一条路径，他们希望至少有两条。当然，他们只能在官方路径上从一个牧场移动到另一个牧场。

给定当前 \(R(F-1\le R\le 10,000)\) 条路径的描述，每条路径恰好连接两个不同的牧场，确定必须修建的最少新路径数量（每条新路径也恰好连接两个牧场），以便在任意一对牧场之间至少有两条独立的路线。若两条路线不使用相同的路径，即使它们沿途访问相同的中间牧场，也被视为独立的。

在同一对牧场之间可能已经有多条路径，你也可以修建一条新路径连接与某条现有路径相同的牧场。

【输入】

第 \(1\) 行：两个用空格分隔的整数：\(F\) 和 \(R\)。

第 \(2\) 行到第 \(R+1\) 行：每行包含两个用空格分隔的整数，表示某条路径的两个端点牧场。

【输出】

第 \(1\) 行：一个整数，表示必须修建的新路径数量。

【输入样例】

【输出样例】

【算法标签】

《洛谷 P2860 Redundant Paths》 #图论# #双连通分量# #USACO# #2006#

【代码详解】

#include <bits/stdc++.h>
using namespace std;

const int N = 5005;        // 最大节点数
const int M = 20005;        // 最大边数（无向图需要两倍空间）

// 边结构体
struct edge
{
    int v;                  // 边的终点
    int ne;                 // 下一条边的索引
} e[M];

int h[N];                   // 邻接表头指针数组
int idx = 1;                // 边索引计数器（从2开始，便于异或操作）

int dfn[N];                 // DFS序（时间戳）
int low[N];                 // 通过回边能到达的最小DFN值
int tot;                    // 时间戳计数器

stack<int> stk;             // Tarjan算法栈

int dcc[N];                 // 存储每个节点所属的边双连通分量编号
int cnt;                    // 边双连通分量计数器

int bri[M];                 // 标记边是否为桥
int d[N];                   // 存储每个边双连通分量的度数

int n, m, a, b;             // n:节点数, m:边数, a,b:临时变量

/**
 * 添加无向边到邻接表
 * @param a 边的起点
 * @param b 边的终点
 */
void add(int a, int b)
{
    e[++idx].v = b;         // 记录边的终点
    e[idx].ne = h[a];       // 新边指向原头节点
    h[a] = idx;             // 更新头节点指向新边
}

/**
 * Tarjan算法求边双连通分量和桥
 * @param x 当前节点
 * @param in_edg 进入当前节点的边索引
 */
void tarjan(int x, int in_edg)
{
    // 初始化当前节点的DFN和LOW值
    dfn[x] = low[x] = ++tot;
    
    // 将当前节点压入栈
    stk.push(x);
    
    // 遍历当前节点的所有邻接节点
    for (int i = h[x]; i; i = e[i].ne)
    {
        int y = e[i].v;     // 邻接节点
        
        // 如果邻接节点y未被访问（树边）
        if (!dfn[y])
        {
            tarjan(y, i);                   // 递归访问y
            low[x] = min(low[x], low[y]);   // 更新low值
            
            // 桥的判断条件：low[y] > dfn[x]
            if (low[y] > dfn[x])
            {
                bri[i] = bri[i ^ 1] = true; // 标记边i和反向边i^1为桥
            }
        }
        // 如果y已被访问且不是来时的边（回边）
        else if (i != (in_edg ^ 1))
        {
            low[x] = min(low[x], dfn[y]);   // 通过回边更新low值
        }
    }
    
    // 如果当前节点是边双连通分量的根
    if (dfn[x] == low[x])
    {
        ++cnt;  // 增加边双连通分量计数
        
        // 弹出栈中节点直到遇到当前节点
        while (true)
        {
            int y = stk.top();
            stk.pop();
            dcc[y] = cnt;   // 记录节点所属的边双连通分量
            if (y == x)
            {
                break;
            }
        }
    }
}

int main()
{
    // 输入节点数和边数
    cin >> n >> m;
    
    // 输入所有边并构建无向图
    while (m--)
    {
        cin >> a >> b;
        add(a, b);  // 添加边a->b
        add(b, a);  // 添加边b->a（无向图需要双向添加）
    }
    
    // 执行Tarjan算法（假设图连通，从节点1开始）
    tarjan(1, 0);
    
    // 统计每个边双连通分量的度数（桥的数量）
    for (int i = 2; i <= idx; i++)
    {
        // 如果当前边是桥
        if (bri[i])
        {
            // 增加目标节点所在分量的度数
            d[dcc[e[i].v]]++;
        }
    }
    
    // 统计度数为1的边双连通分量数量（叶子节点）
    int sum = 0;
    for (int i = 1; i <= cnt; i++)
    {
        if (d[i] == 1)
        {
            sum++;
        }
    }
    
    // 输出需要添加的最少边数：(叶子节点数+1)/2
    cout << (sum + 1) / 2 << endl;
    
    return 0;
}

【运行结果】

posted @ 2026-02-08 18:27 热爱编程的通信人阅读(2) 评论(0) 收藏举报

刷新页面返回顶部

guolianggsta

USACO历年黄金组真题解析 | 2006年1月

P2860 Redundant Paths

公告