Skip to content

Problem H: AFPS

📝 题目描述

🔑 算法模块

💡 思路分析

注意到这是一个正权图，考虑这个算法的反松弛过程：

一旦存在一条某个点出发回到自己的路径（即环路），注意到这条路径的权值（其上所有边的权值和）一定为正，因此沿着这条路径一定会发生一次反松弛，而再次到达之后又会走到这条环路上，结果就是算法无法停机。

因此，如果 \(1\) 号结点能够到达一个环（也就是其所在的连通分量中存在环），答案一定是 \(0\) 。

否则，\(1\) 号结点所在连通分量一定是树，此时距离数组分为两部分：和 \(1\) 号结点在同一连通分量的点，其值为以 \(1\) 为根的树的深度（到 \(1\) 号结点的距离）；其他点由于未被访问到，值为 \(-1\)。

因此找环后验证即可。一种简单的方式是直接 DFS，时间复杂度线性。

也可以在打访问标记的基础上直接使用题目给出的伪代码，注意当有解时这个算法退化为一般树上 BFS，时间复杂度也是线性。

🖥️ 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+11;
using ll=long long;
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int> > > G(n+3);
    vector<ll> evs(m+3,0);
    vector<int> vis(n+3,0);
    vector<ll> d1(n+3,-1),d2(n+3,0);
    d1[1]=0;
    auto dfs=[&](auto &&self,int u,int eid)->bool
    {
        if(vis[u]) return 0;
        vis[u]=1;
        for(auto [v,nxid]:G[u]) if(eid!=nxid)
        {
            if(vis[v]) return 0;
            d1[v]=d1[u]+evs[nxid];
            if(!self(self,v,nxid)) return 0;
        }
        return 1;
    };
    for(int i=1,iu,iv;i<=m;++i)
    {
        ll ival;
        cin>>iu>>iv>>ival;evs[i]=ival;
        G[iu].push_back({iv,i});
        G[iv].push_back({iu,i});
    }
    bool ok=dfs(dfs,1,-1);
    for(int i=1;i<=n;++i) cin>>d2[i];
    if(ok) for(int i=1;i<=n;++i) if(d1[i]^d2[i])
    {
        ok=0;break;
    }
    if(!ok) cout<<0<<'\n';else cout<<1<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

⏱️ 复杂度分析

📚 拓展