AtCoder Beginner Contest 280F

ABC280F

全域木の ポテンシャルを用いた問題．

\(x, y \in V(G)\) をとる．

• Case: \(x,y\) が異なる connected component に属する
  ans = nan.
• Case: \(x,y\) が同じ connected component \(=: H\) に属する
  • Case : あるサイクル \(c\) on \(H\) のコスト が non zero
    サイクルの向きを選べば, path \(x \rightarrow y\) のコストはいくらでも大きくできる． ans = inf.
  • Case : 任意のサイクル \(c\) on \(H\) のコスト が zero
    \(r := \) ( \(H\) の全域木の root ) を任意に fix. このとき， \(cost[x][y]\) は path の取り方に依らず一定． なぜなら，任意のサイクル \(c\) on \(H\) のコストが \(0\) だから， とくに， \(cost[x][y] = - cost[r][x] + cost[r][y]. \)

計算量: \(O(N + M)\)
なぜなら，連結成分毎に DFS をするだけだから．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n, m, q;

  cin >> n >> m >> q;

  vector<vector<pll>> to(n);

  rep(i,m){

    ll a, b,c; cin >> a >> b >> c;

    --a,--b;

    to[a].push_back({b,c});

    to[b].push_back({a,-c});

  }

  vll po(n);

  vll cid(n,-1); ll cn = 0; // id of connected comonents

  vll ary;

  auto dfs = [&](auto f, ll cu, ll pa, ll d = 0) -> void {

    if(cid[cu] != -1){

      if(d != po[cu]) ary.back() = true;

      return;

    }

   

    po[cu] = d;

    cid[cu] = cn;

    for(auto [ne, c]: to[cu]) if(ne != pa){

      f(f, ne, cu, d + c);

    }

  };

 

  rep(i,n)if(cid[i] == -1){

    ary.push_back(false);

    dfs(dfs,i,-1);

    cn++;

  }

  rep(qi,q){

    ll x,y; cin >> x >> y;

    --x,--y;

    assert(cid[x] != -1);

    assert(cid[y] != -1);

    if(cid[x] != cid[y]) cout << "nan" << endl;

    else if(ary[cid[x]]) cout << "inf" << endl;

    else cout << po[y] - po[x] << endl;

  }

  return 0;

}