AtCoder Beginner Contest 280 F - Pay or Receive

小灰灰 2024-03-24 11:02 52阅读 0赞

**蜗册，感觉学到了很多啊**

![312461f5e1884a37b10f05b75316f8a1.png][]

![65dae62efb0148e2bdb755b2feaa9367.png][]

**感谢jd**

**我悟了**

**提一下差点忘记的事实：**

**dij每个点都只被更新一次**

**spfa每个点可以被更新多次**

[F - Pay or Receive (atcoder.jp)][F - Pay or Receive _atcoder.jp]

题意：

![b6742382c95f4399b06262f5746b97dd.png][]

![30cbc79906fc4138b949d299119c344f.png][]

思路：

对于连通性的判断，用并查集就可以维护

对于Inf的判断：当一个连通分量中存在正权环时，该连通分量中的所有点直接都是Inf，这个应该很好想

其余情况直接输出距离即可

那现在的问题，就是如何判正权环

这里的判正权环，是用到了建图的时候的特殊性：

![10a4697b46044daa8bb00623d0ac67b9.png][]

这里用到的结论就是：点与点之间路径唯一

为什么

用反证法，假设路径不唯一

比如点 a 和点 b 直接有两条边：一条x，一条y，其中abs(x)>abs(y)

那么一定存在正权环：x-y

这样就会不断走正权环，所以就Inf了

**那么既然路径唯一，那么最长路就可以用BFS解了，DFS也可以**

在跑BFS的过程中，如果发现了路径不唯一，那么一定存在正权环

注意因为不是连通图，因此需要对每个连通分量都跑一遍BFS

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    const int mxe=1e6+10;
    const int mod=1000007;
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
    int n,m,q,u,v,w,tot=0;
    int f[mxn],head[mxn],bl[mxn],cyc[mxn];
    int dis[mxn],vis[mxn];
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            dis[i]=-1e18;
        }
    }
    void bfs(int s){
        queue<int> Q;
        Q.push(s);
        dis[s]=0;
        vis[s]=1;
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]==-1e18){
                    dis[edge[i].to]=dis[u]+edge[i].w;
                    Q.push(edge[i].to);
                    vis[edge[i].to]=1;
                }
                if(dis[edge[i].to]!=dis[u]+edge[i].w){
                    cyc[find(edge[i].to)]=1;
                    return;
                }
            }
        }
    }
    void solve(){
        cin>>n>>m>>q;
        G_init();
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,-w);
            join(u,v);
        }
        for(int i=1;i<=n;i++){
            if(vis[find(i)]) continue;
            vis[find(i)]=1;
            bfs(find(i));
        }
        while(q--){
            cin>>u>>v;
            if(find(u)!=find(v)) cout<<"nan"<<'\n';
            else if(cyc[find(u)]==1) cout<<"inf"<<'\n';
            else cout<<dis[v]-dis[u]<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[312461f5e1884a37b10f05b75316f8a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a14e0ccfcfd8472088acd8e54aaade89.png
[65dae62efb0148e2bdb755b2feaa9367.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/8f7cca8e6cc84d8abd63537d1493fb21.png
[F - Pay or Receive _atcoder.jp]: https://atcoder.jp/contests/abc280/tasks/abc280_f
[b6742382c95f4399b06262f5746b97dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6157b08afd8c468c8adc83f9d1d43fb4.png
[30cbc79906fc4138b949d299119c344f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ad7d57523a914a238cceb76810e61342.png
[10a4697b46044daa8bb00623d0ac67b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2ec1c9ee98a24dd4b682fc2ee5dcdbca.png