指挥网络问题

解题思路

关于朱刘算法请参考前置知识：最小树形图算法的相关概念

本题是一个有向图的最小生成树问题，是朱刘算法的模板题，直接套模板即可。

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef pair<double, double> PDD;

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

int n, m;
PDD a[N]; //记录所有点的坐标
bool g[N][N]; //邻接矩阵
double d[N][N], bd[N][N]; //记录每两个点之间的距离、备份
int pre[N]; //记录每个点选择的前驱点
int dfn[N], low[N], timestamp; //tarjan 算法的数组
int stk[N], top; //栈
bool in_stk[N]; //记录每个点是否在栈中
int id[N], cnt; //记录每个点所在的强连通分量编号
bool st[N]; //记录每个点能否从 1 号点搜索到

void dfs(int u) //从 u 节点往下搜索所有点
{
    st[u] = true;

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

bool check() //判断整个图是否具有连通性
{
    memset(st, 0, sizeof st); //初始化
    dfs(1); //从 1 号点开始搜索所有点

    for(int i = 1; i <= n; i++)
        if(!st[i])
            return false; //如果某个点搜不到，说明图不连通
    return true; //否则说明连通
}

double get_dist(int i, int j) //计算两个点之间的距离
{
    double x = a[i].first - a[j].first;
    double y = a[i].second - a[j].second;
    return sqrt(x * x + y * y);
}

void tarjan(int u) //tarjan 算法缩点
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;

    //由于每个点只有一条入边，不需要循环
    int j = pre[u];
    if(!dfn[j])
    {
        tarjan(j);
        low[u] = min(low[u], low[j]);
    }
    else if(in_stk[j]) low[u] = min(low[u], dfn[j]);

    //找到一个环
    if(dfn[u] == low[u])
    {
        int y;
        cnt++;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = cnt;
        } while(y != u);
    }
}

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; //不存在边，距离为 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);
        timestamp = top = cnt = 0;

        //tarjan 算法求环
        for(int i = 1; i <= n; i++)
            if(!dfn[i])
                tarjan(i);

        if(cnt == n) //如果缩点后还是 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];
                    //如果 j 和 j 的前驱点在同一个强连通分量中，说明该边的终点 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;
}

int main()
{
    while(scanf("%d%d", &n, &m) != -1)
    {
        for(int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].first, &a[i].second);

        memset(g, 0, sizeof g); //初始化
        while(m--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            if(a != b && b != 1) g[a][b] = true; //边不能存在自环，且回到 1 的边不用存
        }

        if(!check()) puts("poor snoopy"); //如果图不连通，说明无解
        else printf("%.2lf\n", work()); //否则说明有解，输出答案
    }
    return 0;
}