题解：银河问题

一、题目背景

有 (N) 颗被关注的恒星，每颗恒星的亮度用正整数表示，最暗为 (1) 。已知 (M) 对恒星之间的亮度相对关系，包括亮度相等、大于、小于、不小于、不大于等情况。需要求出这 (N) 颗恒星的亮度值总和至少是多少。

二、解题思路

本题通过构建差分约束系统，利用Tarjan算法和拓扑排序（这里通过倒序遍历缩点后的图实现类似拓扑排序的效果）来求解。将每颗恒星看作一个节点，根据恒星之间的亮度关系构建有向边，然后通过Tarjan算法找出强连通分量，判断是否存在矛盾关系（即强连通分量内存在权值大于 (0) 的边），若存在则无解；若不存在，则在缩点后的图上计算每个强连通分量的亮度值，最后求出所有恒星亮度值总和的最小值。

具体步骤如下：
1. 定义图的存储结构，包括原始图邻接表 h[N]、缩点后图邻接表 hs[N]、边的终点数组 e[M]、下一条边的指针数组 ne[M]、边权数组 w[M]、时间戳数组 dfn[N]、追溯数组 low[N]、栈数组 stk[N] 及栈顶指针 top、节点是否在栈中的标记数组 in_stk[N]、节点所属强连通分量编号数组 id[N]、强连通分量数量 scc_cnt、每个强连通分量的大小数组 sz[N]、每个强连通分量的亮度值数组 dist[N]。
2. 编写添加边的函数 add，用于构建邻接表。
3. 实现Tarjan算法函数 tarjan，用于找出图中的强连通分量：
- 更新当前节点的 dfn 和 low 值，并将节点入栈，标记在栈中。
- 遍历当前节点的邻接边，对于未访问的节点，递归调用 tarjan 并更新 low 值；对于已访问且在栈中的节点，更新 low 值。
- 若当前节点的 dfn 和 low 值相等，则表示找到了一个强连通分量，将栈中节点弹出，标记不在栈中，并记录所属强连通分量编号和大小。
4. 在 main 函数中：
- 读取恒星数量 n 和关系数量 m，初始化邻接表。
- 添加从虚拟源点 0 到每颗恒星的边，边权为 (1)，表示每颗恒星亮度至少为 (1)。
- 读取每对恒星的关系，根据关系类型构建图的邻接表。
- 对虚拟源点 0 调用Tarjan算法，找出所有强连通分量。
- 检查强连通分量内是否存在矛盾关系（权值大于 (0) 的边），若存在则标记无解；否则，构建缩点后的图。
- 若有解，从后往前遍历缩点后的图的每个强连通分量，更新其邻接强连通分量的亮度值。
- 计算所有恒星亮度值总和的最小值，即每个强连通分量的亮度值乘以其大小的总和。
- 输出结果，若无解输出 (-1)，否则输出亮度值总和的最小值。

三、代码逐段分析

（一）头文件和全局变量

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

using namespace std;

typedef long long LL;

const int N = 100010, M = 600010;

int n, m;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, sz[N];
int dist[N];

1. 头文件：
   • #include <cstdio>：用于标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 类型定义：typedef long long LL; 定义 LL 为 long long 类型，方便后续使用。
3. 常量定义：
   • const int N = 100010, M = 600010;：定义节点的最大数量（恒星数量加虚拟源点）和边的最大数量。
4. 变量定义：
   • int n, m;：分别表示恒星的数量和亮度关系的数量。
   • int h[N], hs[N], e[M], ne[M], w[M], idx;：h[N] 是原始图邻接表头指针数组，hs[N] 是缩点后图邻接表头指针数组，e[M] 存储边的终点，ne[M] 存储下一条边的指针，w[M] 存储边权，idx 用于边的编号。
   • int dfn[N], low[N], timestamp;：dfn[N] 记录节点首次访问的时间戳，low[N] 记录节点或其子孙能追溯到的最早时间戳，timestamp 是时间戳计数器。
   • int stk[N], top;：stk[N] 是栈数组，top 是栈顶指针。
   • bool in_stk[N];：标记每个节点是否在栈中。
   • int id[N], scc_cnt, sz[N];：id[N] 记录节点所属强连通分量编号，scc_cnt 是强连通分量数量，sz[N] 存储每个强连通分量的大小。
   • int dist[N];：记录每个强连通分量的亮度值。

（二）添加边函数

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

该函数用于向邻接表中添加一条边，参数 h[] 表示邻接表头指针数组，a 为起点，b 为终点，c 为边权。通过更新邻接表数组，将边的信息存储起来。

（三）Tarjan算法函数

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

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        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])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt] ++ ;
        } while (y != u);
    }
}

1. 初始化当前节点的 dfn 和 low 值为当前时间戳，将节点入栈并标记在栈中。
2. 遍历当前节点的邻接边：
   • 若邻接节点未访问，递归调用 tarjan 函数，并更新当前节点的 low 值为当前 low 值和邻接节点 low 值的较小值。
   • 若邻接节点已访问且在栈中，更新当前节点的 low 值为当前 low 值和邻接节点 dfn 值的较小值。
3. 若当前节点的 dfn 和 low 值相等，说明找到了一个强连通分量：
   • 强连通分量数量加 (1)。
   • 从栈中弹出节点，标记不在栈中，记录所属强连通分量编号，增加对应强连通分量的大小。

（四）main 函数

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);

    for (int i = 1; i <= n; i ++ ) add(h, 0, i, 1);

    while (m -- )
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if (t == 1) add(h, b, a, 0), add(h, a, b, 0);
        else if (t == 2) add(h, a, b, 1);
        else if (t == 3) add(h, b, a, 0);
        else if (t == 4) add(h, b, a, 1);
        else add(h, a, b, 0);
    }

    tarjan(0);

    bool success = true;
    for (int i = 0; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a == b)
            {
                if (w[j] > 0)
                {
                    success = false;
                    break;
                }
            }
            else add(hs, a, b, w[j]);
        }
        if (!success) break;
    }

    if (!success) puts("-1");
    else
    {
        for (int i = scc_cnt; i; i -- )
        {
            for (int j = hs[i]; ~j; j = ne[j])
            {
                int k = e[j];
                dist[k] = max(dist[k], dist[i] + w[j]);
            }
        }

        LL res = 0;
        for (int i = 1; i <= scc_cnt; i ++ ) res += (LL)dist[i] * sz[i];

        printf("%lld\n", res);
    }

    return 0;
}

1. 读取恒星数量 n 和关系数量 m，初始化原始图和缩点后图的邻接表。
2. 添加从虚拟源点 0 到每颗恒星的边，边权为 (1)。
3. 读取每对恒星的关系，根据关系类型在原始图邻接表中添加边。
4. 对虚拟源点 0 调用Tarjan算法，找出所有强连通分量。
5. 检查强连通分量内是否存在矛盾关系：
   • 遍历原始图的边，若两个端点属于同一个强连通分量且边权大于 (0)，则标记无解。
   • 否则，将边添加到缩点后的图的邻接表中。
6. 若无解，输出 (-1)；否则：
   • 从后往前遍历缩点后的图的每个强连通分量，更新其邻接强连通分量的亮度值。
   • 计算所有恒星亮度值总和的最小值，即每个强连通分量的亮度值乘以其大小的总和。
   • 输出结果。
7. 程序结束。

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

（一）时间复杂度

1. 建图：读取 (m) 条关系构建原始图邻接表，时间复杂度为 (O(m))。
2. Tarjan算法：每个节点最多被访问一次，每条边最多被遍历一次，时间复杂度为 (O(n + m))。
3. 检查矛盾和缩点建图：遍历 (m) 条边检查矛盾关系和构建缩点后的图邻接表，时间复杂度为 (O(m))。
4. 计算亮度值和结果：遍历缩点后图的边更新亮度值，时间复杂度为 (O(m’))，其中 (m’) 是缩点后图的边数，(m’\leq m)；遍历 (scc_cnt) 个强连通分量计算结果，时间复杂度为 (O(scc_cnt))，(scc_cnt\leq n)。
   总体时间复杂度为 (O(n + m))。

（二）空间复杂度

1. 邻接表：存储原始图和缩点后图的边信息，空间复杂度为 (O(m))。
2. 其他数组：时间戳数组 dfn[N]、追溯数组 low[N]、栈数组 stk[N]、节点是否在栈中的标记数组 in_stk[N]、节点所属强连通分量编号数组 id[N]、强连通分量数量 scc_cnt、每个强连通分量的大小数组 sz[N]、每个强连通分量的亮度值数组 dist[N]，空间复杂度均为 (O(n))。
   总体空间复杂度为 (O(n + m))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。