题解：AT_abc280_f [ABC280F] Pay or Receive

liyao2025 · 2025-05-22 13:30:40 · 题解

题目大意

有一张有向图，其中 \text{n} 个顶点，\text{2m} 条边。第 \text{i} 条边连接 a_{i} 和 b_{i}，其中从 a_{i} 到 b_{i} 的权值为 c_{i}，从 b_{i} 到 a_{i} 的权值为 -c_{i}。给出 Q 个问题：

从 X_{i} 到 Y_{i} 时的最大得分。
如果 X_{i} 与 Y_{i} 不在一个子图里，输出 nan。
如果 X_{i} 到 Y_{i} 的分数可以是无限，输出 inf。

注：本题解的子图可以理解为强连通分量。

思路

分析

这是‌最长路‌问题，根据题意，输出有 3 种情况。

‌第一种情况‌：需 a_i 与 b_i 在同一子图中。
‌第二种情况‌：a_i 与 b_i 不在同一子图，输出 nan。
‌第三种情况‌：子图存在正环，输出 inf。

解法

首先我们需要了解图的两个知识。

如下图，我们举个例子，我们问从 1 号点到 6 号点的最大距离是多少？很容易看出 1 号点到 6 号有两条路径，通过观察，我们易得，只要到终点的其中两条路径不相等，则这个子图是正环，也就是子图内的所有点的到图内任意点的距离都是可以无限刷分的。

直接暴力搜图的肯定是不行的，所以我想到的一个类似前缀和的方法。还是那个图，如果我们问 4 号点到 5 号点的最长路，我们就可以用 1 到 5 号点的最长路减 1 到 4 号点的最长路，即 l[y] - l[x] 其中 l[] 为 1 到 x 点的最长路。

按上述枚举一遍边，最后输出答案。

代码


#include<bits/stdc++.h>
using namespace std;
// 表示从一个节点到另一个节点的有向边
struct node 
{   
    long long to, z;     // to: 目标节点, z: 边的权值 
};

vector<node> v[1000009];
long long n, m, q, x, y, t;
long long l[1000009];  // l[]: 节点 i 在当前子图中的基准得分
long long j[1000009];  // j[]: 节点 i 所属的子图编号
long long cnt;         // cnt: 当前子图的编号
long long p[1000009];  // p[]: 标记子图 i 是否存在正环（可获得无限分数）
bool f[1000009];  

void dfs(long long dis)
{
    j[dis] = cnt;  
    f[dis] = true;  
    long long len = v[dis].size();  
    for(long long i = 0; i < len; i++)  // 遍历所有边
    {
        long long u = v[dis][i].to;  
        if(f[u] == false)  // 如果目标节点未被访问
        {
            l[u] = l[dis] + v[dis][i].z;  
            dfs(u);  
        }
        else if(l[u] != l[dis] + v[dis][i].z)  // 说明存在正环
            p[cnt] = 1;  // 标记当前子图存在正环
    }
    return ;
}

int main()
{
    scanf("%lld%lld%lld", &n, &m, &q); 
    for(long long i = 1; i <= m; i++) 
    {
        scanf("%lld%lld%lld", &x, &y, &t);
        node p; 
        p.to = y, p.z = t;  // 设置正向边（x->y，得分为 t）
        v[x].push_back(p); 
        p.to = x, p.z = -t;  // 设置反向边（y->x，得分为 -t）
        v[y].push_back(p); 
    }

    for(long long i = 1; i <= n; i++)  // 遍历所有节点，处理各个子图
        if(f[i] == false)  // 如果节点 i 未被访问（属于新的子图）
        {    
            cnt++;  // 子图编号加 1
            dfs(i);  // 从节点 i 开始深度优先搜索
        }

    while(q--)
    {
        scanf("%lld%lld", &x, &y); 
        if(j[x] != j[y])  // 如果两个节点不在同一个子图中
            printf("nan\n");
        else if(p[j[x]])  // 存在正环
            printf("inf\n");
        else printf("%lld\n", l[y] - l[x]); 
    }
    return 0;
}