题解：指挥网络

一、题目分析

本题背景是利特肯王国和克努斯海洋王国爆发战争，利特肯王国指挥网络瘫痪，需要建立临时指挥网络，使得利特肯所在的指挥总部（节点1）的命令能够传达至平面中的每个节点。已知节点总数(N)，部分节点间可建立单向传输电线，且每个节点有坐标，要求计算出能满足要求的最短电线总长度。

二、解题思路

本题通过构建图论模型，利用有向图的最小树形图算法（朱刘算法）来求解。

（一）图的构建与连通性检查

• 构建邻接矩阵g：根据输入的可建立电线的节点对信息，将对应的g[a][b]设为true，表示可以从节点a到节点b建立单向电线。
• 检查连通性：通过深度优先搜索dfs从节点1出发，标记访问过的节点。遍历所有节点，若存在未被访问的节点，则说明图不连通，直接输出“poor snoopy”，表示无法建立满足要求的指挥网络；若所有节点都能被访问到，则说明图是连通的，可以继续后续操作。

（二）计算节点间距离与初始化

• 计算距离函数get_dist：根据两个节点的坐标，利用欧几里得距离公式计算它们之间的直线距离。
• 初始化距离矩阵d：遍历所有节点对，若节点间可以建立电线，则将d[i][j]设为它们之间的距离；否则设为一个极大值INF。

（三）朱刘算法求最小树形图

朱刘算法用于在有向图中寻找以指定节点为根的最小树形图（最小生成树的有向图版本），步骤如下：
1. 找最小入边：对于每个节点i（除根节点外），在所有指向它的边中找到距离最小的边，记录这条边的起点为pre[i]。
2. 判断是否为最小树形图：使用Tarjan算法求强连通分量。若图中的强连通分量个数等于节点个数，说明每个节点都在独立的强连通分量中，即找到了最小树形图，将所有最小入边的距离相加得到结果并结束算法；否则说明存在环，进入下一步。
3. 处理环：
- 对于在同一个强连通分量中的节点i，将其最小入边的距离累加到结果res中。
- 构建新的距离矩阵bd，对于不在同一个强连通分量的节点对(i, j)，根据一定规则更新bd[id[i]][id[j]]的值（主要考虑环内节点的情况，对边的距离进行调整）。
- 将节点数更新为强连通分量的个数cnt，并将距离矩阵d更新为bd，重复步骤1。

（四）输出结果

若图连通，通过朱刘算法计算出最小树形图的总长度，按照保留两位小数的格式输出；若图不连通，则输出“poor snoopy”。

三、代码实现细节

（一）头文件与全局变量

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 110;
const double INF = 1e8;

int n, m;
PDD q[N];
bool g[N][N];
double d[N][N], bd[N][N];
int pre[N], bpre[N];
int dfn[N], low[N], ts, stk[N], top;
int id[N], cnt;
bool st[N], ins[N];

• 引入输入输出、字符串操作、标准输入输出、算法和数学相关头文件。
• 定义常量N表示节点数上限，INF表示极大值。
• 定义变量n为节点总数，m为可建立电线的节点对数。
• 定义PDD类型的数组q存储节点的坐标。
• 定义邻接矩阵g表示节点间是否可以建立电线。
• 定义距离矩阵d和临时距离矩阵bd。
• 定义pre数组记录每个节点的最小入边起点，bpre数组未使用。
• 定义Tarjan算法相关数组dfn、low、ts、stk、top、id、cnt以及标记数组st、ins。

（二）深度优先搜索函数dfs

void dfs(int u)
{
    st[u] = true;
    for (int i = 1; i <= n; i ++ )
        if (g[u][i] &&!st[i])
            dfs(i);
}

从节点u开始深度优先搜索，标记访问过的节点。

（三）检查连通性函数check_con

bool check_con()
{
    memset(st, 0, sizeof st);
    dfs(1);
    for (int i = 1; i <= n; i ++ )
        if (!st[i])
            return false;
    return true;
}

调用dfs从节点1开始搜索，然后检查所有节点是否都被访问过，判断图是否连通。

（四）计算距离函数get_dist

double get_dist(int a, int b)
{
    double dx = q[a].x - q[b].x;
    double dy = q[a].y - q[b].y;
    return sqrt(dx * dx + dy * dy);
}

根据节点a和b的坐标，利用欧几里得距离公式计算它们之间的距离。

（五）Tarjan算法函数tarjan

void tarjan(int u)
{
    dfn[u] = low[u] = ++ ts;
    stk[ ++ top] = u, ins[u] = true;

    int j = pre[u];
    if (!dfn[j])
    {
        tarjan(j);
        low[u] = min(low[u], low[j]);
    } else if (ins[j]) low[u] = min(low[u], dfn[j]);

    if (low[u] == dfn[u])
    {
        int y;
        ++ cnt;
        do
        {
            y = stk[top -- ], ins[y] = false, id[y] = cnt;
        } while (y != u);
    }
}

• 开始时初始化dfn[u]和low[u]，将u入栈并标记在栈中。
• 根据节点pre[u]的情况更新low[u]。
• 当low[u] = dfn[u]时，弹出栈中节点并标记它们属于同一个强连通分量。

（六）朱刘算法函数work

double work()
{
    double res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (g[i][j]) d[i][j] = get_dist(i, j);
            else d[i][j] = INF;

    while (true)
    {
        for (int i = 1; i <= n; i ++ )
        {
            pre[i] = i;
            for (int j = 1; j <= n; j ++ )
                if (d[pre[i]][i] > d[j][i])
                    pre[i] = j;
        }

        memset(dfn, 0, sizeof dfn);
        ts = cnt = 0;
        for (int i = 1; i <= n; i ++ )
            if (!dfn[i])
                tarjan(i);

        if (cnt == n)
        {
            for (int i = 2; i <= n; i ++ ) res += d[pre[i]][i];
            break;
        }

        for (int i = 2; i <= n; i ++ )
            if (id[pre[i]] == id[i])
                res += d[pre[i]][i];

        for (int i = 1; i <= cnt; i ++ )
            for (int j = 1; j <= cnt; j ++ )
                bd[i][j] = INF;

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (d[i][j] < INF && id[i] != id[j])
                {
                    int a = id[i], b = id[j];
                    if (id[pre[j]] == id[j]) bd[a][b] = min(bd[a][b], d[i][j] - d[pre[j]][j]);
                    else bd[a][b] = min(bd[a][b], d[i][j]);
                }

        n = cnt;
        memcpy(d, bd, sizeof d);
    }

    return res;
}

• 初始化距离矩阵d。
• 进入循环，每次循环执行朱刘算法的步骤：找最小入边、判断是否为最小树形图、处理环（若存在）。
• 若找到最小树形图，返回总长度；否则更新相关变量继续循环。

（七）main函数

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);

        memset(g, 0, sizeof g);
        while (m -- )
        {
            int a, b;
            scanf("%d%d", &a, &b);
            if (a != b && b != 1) g[a][b] = true;
        }

        if (!check_con()) puts("poor snoopy");
        else printf("%.2lf\n", work());
    }

    return 0;
}

• 循环读取测试数据，包括节点总数n和可建立电线的节点对数m。
• 读取每个节点的坐标，初始化邻接矩阵g并根据输入更新。
• 检查图的连通性，若不连通输出“poor snoopy”；若连通调用work函数计算并输出最小树形图的总长度。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 建图与连通性检查阶段：初始化邻接矩阵时间复杂度为(O(n^2))，检查连通性通过深度优先搜索，时间复杂度为(O(n + m))（(m)为边数），整体时间复杂度为(O(n^2 + n + m))，近似为(O(n^2))。
• 朱刘算法阶段：每次循环中找最小入边时间复杂度为(O(n^2))，Tarjan算法求强连通分量时间复杂度为(O(n + m))，处理环的操作时间复杂度也为(O(n^2))。由于最多循环(n)次（每次循环节点数可能减少），所以朱刘算法总时间复杂度为(O(n \times (n^2 + n + m)))，近似为(O(n^3))。
• 因此，总的时间复杂度为(O(n^3))。

（二）空间复杂度

• 邻接矩阵g占用空间为(O(n^2))。
• 距离矩阵d和临时距离矩阵bd占用空间为(O(n^2))。
• 其他辅助数组如pre、dfn、low等占用空间为(O(n))。
• 所以，总的空间复杂度为(O(n^2))。