Intelligence System

样例

digraph ALPC_Intelligence_System {
    // 设置图的通用属性
    rankdir=LR;
    fontname="Arial";
    node [shape=circle, style=filled, fillcolor=lightgrey, fontname="Arial"];
    edge [fontname="Arial"];

    // ================= Sample 1 =================
    subgraph cluster_sample1 {
        label = "Sample 1\nResult Cost: 150";
        style = rounded;
        bgcolor = "#f9f9f9";

        // 定义节点，使用前缀s1_防止冲突
        s1_0 [label="0\n(Root)"];
        s1_1 [label="1"];
        s1_2 [label="2"];

        // 边
        s1_0 -> s1_1 [label="100", color="red", penwidth=2.5]; // 选中
        s1_1 -> s1_2 [label="50", color="red", penwidth=2.5];  // 选中
        s1_0 -> s1_2 [label="100", style="dashed", color="grey"]; // 未选中
    }

    // ================= Sample 2 =================
    subgraph cluster_sample2 {
        label = "Sample 2\nResult Cost: 100\n(Nodes 1 & 2 form a Branch)";
        style = rounded;
        bgcolor = "#f9f9f9";

        s2_0 [label="0\n(Root)"];

        // 使用子图来表示强连通分量 (Branch)
        subgraph cluster_scc {
            label = "Branch (SCC)\nInternal Cost Ignored";
            style = dashed;
            color = blue;
            node [fillcolor=lightblue];
            s2_1 [label="1"];
            s2_2 [label="2"];
            
            // 环内的边，虽然在物理上存在，但在计算进入成本时被视为内部循环
            s2_1 -> s2_2 [label="50", color="black"];
            s2_2 -> s2_1 [label="100", color="black"];
        }

        // 选中的是进入该连通分量的边
        s2_0 -> s2_1 [label="100", color="red", penwidth=2.5]; 
    }

    // ================= Sample 3 =================
    subgraph cluster_sample3 {
        label = "Sample 3\nResult Cost: 50";
        style = rounded;
        bgcolor = "#f9f9f9";

        s3_0 [label="0\n(Root)"];
        s3_1 [label="1"];

        s3_0 -> s3_1 [label="50", color="red", penwidth=2.5]; // 较小的边
        s3_0 -> s3_1 [label="100", style="dashed", color="grey"]; // 较大的边
    }
}

题目解析

这道题是 HDU 1827 - Ultimate Intelligence。

这是一道非常经典的图论题目，考察的是 强连通分量 (SCC) 缩点 和贪心思想。

1. 题目大意与核心分析

题意：

ALPC 情报网需要传递情报。情报由 kzc_tc (编号为 0) 发出，需要传达给所有人。

传递是单向的，从 $X$ 到 $Y$ 有费用 $C$ 。
关键规则：如果两个人在同一个“分支”（即互相可以直接或间接传递消息，也就是构成强连通分量 SCC），那么他们之间的传递费用可以被忽略（费用为 0）。
问：保证所有人都能收到情报的 最小总费用 是多少。

核心考点：

强连通分量 (SCC)：题目中“互相可以传递…费用忽略”描述的就是 SCC 的性质。在同一个 SCC 内部，只要有一个人收到了消息，其他人都能免费收到。
DAG 上的贪心：将图中的 SCC 缩成一个点后，原图变成了一个 有向无环图 (DAG)。
最小树形图 (简化版)：我们需要在一个 DAG 上选择边，使得根节点（SCC 0）能到达所有其他 SCC。

2. 算法逻辑解析

因为同一个 SCC 内部通信花费为 0，我们可以把每个 SCC 看作一个超级节点。

步骤 1：Tarjan 算法缩点

使用 Tarjan 算法找出所有的 SCC。记录每个点所属的 SCC 编号 (scc_id)。

步骤 2：构建缩点后的图（虚拟构建）

缩点后，我们只关心 SCC 之间的边。

对于原图中的每一条边 $u \to v$ (花费 $w$ )：

如果 $u$ 和 $v$ 在同一个 SCC ( $scc\_id[u] == scc\_id[v]$ )：这条边是内部边，费用忽略，跳过。
如果不在同一个 SCC ( $scc\_id[u] \neq scc\_id[v]$ )：这是一条从 SCC A 到 SCC B 的边，费用为 $w$ 。这意味着只要 SCC A 收到消息，付出 $w$ 的代价，SCC B 就能收到消息。

步骤 3：贪心策略计算最小费用

现在问题变成了：在 DAG 图中，根节点（包含起点 0 的 SCC）已经有消息了，如何以最小代价让其他所有 SCC 都收到消息？

对于 DAG 中的每一个非根 SCC 节点，它必须至少有一个“入边”来源。
为了总费用最小，对于每个 SCC，我们只需要选择所有指向它的边中费用最小的那一条即可。
为什么不需要复杂的最小树形图算法（如朱-刘算法）？

朱-刘算法是为了处理带权环的。但这道题里，所有的环（SCC）都被缩成点了，且内部费用为 0。剩下的图是 DAG。在 DAG 上，贪心选择每个点的最小入边，一定不会构成环，且一定最优。

算法总结：

Ans = \sum_{i \in All\_SCCs, i \neq Root\_SCC} \min(\text{incoming edge cost to } i)

3. 代码实现(超时)

不知道为什么超时 ,在HDU的机器上面

cpp

/**
 * Problem: HDU 1827 - Ultimate Intelligence
 * Analysis: Tarjan SCC + Greedy on DAG
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 50005;   // N <= 50000
const int maxm = 100005;  // M <= 100000
const int INF = 0x3f3f3f3f;

struct Edge {
    int u, v, w, next;
} e[maxm];
int head[maxn], e_cnt;

void init_edge() {
    memset(head, -1, sizeof(head));
    e_cnt = 0;
}

void add_edge(int u, int v, int w) {
    e[e_cnt] = {u, v, w, head[u]};
    head[u] = e_cnt++;
}

struct TarjanSolver {
    int dfn[maxn], low[maxn], timer;
    int stack[maxn], top;
    bool in_stack[maxn];
    
    int scc_id[maxn]; // 每个点所属的 SCC 编号
    int scc_cnt;      // SCC 总数

    // 记录进入某个 SCC 的最小花费
    // min_in_cost[i] 表示进入 SCC i 的最小边权
    int min_in_cost[maxn]; 

    void init(int n) {
        timer = scc_cnt = top = 0;
        for(int i = 0; i <= n; i++) {
            dfn[i] = low[i] = 0;
            in_stack[i] = false;
            min_in_cost[i] = INF; // 初始化为无穷大
        }
    }

    void tarjan(int u) {
        dfn[u] = low[u] = ++timer;
        stack[++top] = u;
        in_stack[u] = true;

        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (in_stack[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }

        if (dfn[u] == low[u]) {
            scc_cnt++;
            while (true) {
                int v = stack[top--];
                in_stack[v] = false;
                scc_id[v] = scc_cnt;
                if (u == v) break;
            }
        }
    }

    void solve(int n, int m) {
        // 1. 求 SCC
        for(int i = 0; i < n; i++) {
            if(!dfn[i]) tarjan(i);
        }

        // 2. 遍历所有边，计算每个 SCC 的最小入边花费
        int start_scc = scc_id[0]; // 起点 0 所在的 SCC

        for(int i = 0; i < m; i++) {
            int u = e[i].u;
            int v = e[i].v;
            int w = e[i].w;

            // 如果这条边连接了两个不同的 SCC
            if(scc_id[u] != scc_id[v]) {
                int target = scc_id[v];
                // 更新进入 target SCC 的最小费用
                if(w < min_in_cost[target]) {
                    min_in_cost[target] = w;
                }
            }
        }

        // 3. 统计答案
        int total_cost = 0;
        for(int i = 1; i <= scc_cnt; i++) {
            // 如果是起点所在的 SCC，不需要花费（本身就有情报）
            if(i == start_scc) continue;
            
            // 累加最小入边花费
            // 题目保证一定有解，所以 min_in_cost[i] 不会是 INF
            total_cost += min_in_cost[i];
        }

        printf("%d\n", total_cost);
    }
} solver;

int main() {
    int n, m;
    while(scanf("%d %d", &n, &m) == 2) {
        init_edge();
        solver.init(n);

        for(int i = 0; i < m; i++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            add_edge(u, v, w);
        }

        solver.solve(n, m);
    }
    return 0;
}

代码(AC)

这个代码可以AC

cpp

/**
 * Problem: HDU 3072 Intelligence System
 * Status: AC
 * Method: Tarjan + SCC缩点 + 贪心
 * Note: 使用 Vector 存图利用缓存局部性，通过 memset 快速初始化
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

const int N = 50010;
const int INF = 0x3f3f3f3f;

int dfn[N], low[N], bel[N], val[N];
bool instack[N];
vector<int> adj[N], cost[N]; // 使用vector存图
stack<int> st; // 使用STL栈
int scc_cnt, idx, n, m;

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    instack[u] = true;
    st.push(u);
    
    // 遍历所有出边
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    // 发现强连通分量
    if (dfn[u] == low[u]) {
        int v;
        scc_cnt++;
        do {
            v = st.top();
            st.pop();
            instack[v] = false;
            bel[v] = scc_cnt;
        } while (u != v);
    }
}

int main() {
    // 关闭同步流，加速 cin/cout
    ios::sync_with_stdio(0);
    cin.tie(0);

    while (cin >> n >> m) {
        // 1. 初始化
        // 对于大数据量的多组测试，memset 通常比手动循环赋值更加底层优化
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(bel, 0, sizeof(bel));
        memset(instack, false, sizeof(instack));
        
        // 清空邻接表
        for (int i = 0; i < n; i++) {
            adj[i].clear();
            cost[i].clear();
            val[i] = INF; // 这里的 val 初始化其实在后面会被覆盖，但保持原逻辑
        }
        
        // 清空栈（防止上一组数据残留）
        while (!st.empty()) st.pop();
        scc_cnt = idx = 0;

        // 2. 读入边
        for (int i = 0; i < m; i++) {
            int u, v, c;
            cin >> u >> v >> c;
            adj[u].push_back(v);
            cost[u].push_back(c);
        }

        // 3. Tarjan 缩点
        for (int i = 0; i < n; i++) {
            if (!dfn[i]) {
                tarjan(i);
            }
        }

        // 4. 初始化每个 SCC 的最小入边权值
        for (int i = 1; i <= scc_cnt; i++) {
            val[i] = INF;
        }

        // 5. 遍历所有边，计算缩点后的最小入边
        for (int u = 0; u < n; u++) {
            for (int j = 0; j < adj[u].size(); j++) {
                int v = adj[u][j];
                int scc_u = bel[u];
                int scc_v = bel[v];
                
                // 如果边连接两个不同的 SCC，更新目标 SCC 的最小入边花费
                if (scc_u != scc_v) {
                    val[scc_v] = min(val[scc_v], cost[u][j]);
                }
            }
        }

        // 6. 计算总成本
        int ans = 0;
        for (int i = 1; i <= scc_cnt; i++) {
            // 关键逻辑：排除包含节点0（起点）的SCC，因为它不需要被通知（它是消息源）
            // 并且过滤掉不可达的INF（虽然题目保证连通，但加上保险）
            if (i != bel[0] && val[i] != INF) { 
                ans += val[i];
            }
        }
        
        cout << ans << endl;
    }
    return 0;
}

复杂度分析

时间复杂度：
- Tarjan 缩点： $O(N + M)$ 。
- 遍历边更新最小花费： $O(M)$ 。
- 统计结果： $O(N)$ 。
- 总计： $O(N + M)$ 。对于 $N=50000, M=100000$ 来说非常快。
空间复杂度：
- 图存储和 Tarjan 辅助数组： $O(N + M)$ 。

易错点提示

起点判断：虽然题目说要传给所有人，但实际上情报是从 kzc_tc (节点0) 开始扩散的。所以 节点0 所在的 SCC 入度费用视为 0（或者直接不加入统计）。
重边处理：两个 SCC 之间可能有多条边，一定要取 min。代码中 min_in_cost[target] = min(...) 处理了这种情况。
多组数据：HDU 的题目通常是多组数据，记得初始化（init_edge 和 solver.init）。

目录

样例