久しぶりの投稿です。。だいぶC問題の正答率が安定した(新ABCになってCの難易度が下がった気もしない。。)ので、D問題の使用しているアルゴリズムと考え方をまとめていこうかなと思います。

ABC061

Score Attack

問題は以下から

枝に重みのついたグラフが与えられて1 ~ N までの頂点に行く際の最大スコアを算出するという問題ですね。

この時 1 ~ N までの経路は非連結でないことは保証されているようです。

最初考えたこと

DFSで閉路を探索
閉路の場合 -> inf
閉路でない場合 -> DFSの経路を全探索して最大を見つける

残念なことにこれではできなかったです。。

与えられる重みは整数なので負の閉路を見つけた場合にinfにはならない
DFS での全探索は頂点の累乗で計算量が増えるので、間に合わない

となったので、解説に頼りました。

読んでみると、ベルマンフォード法を使えばいいようですね。

ダイクストラ法やワーシャル・フロイド法などと同じで聞いたことあるけど実装したことないやつだったのでいい経験になりそうです。

ベルマンフォードの適用問題がわからないので、調べました。

最短経路問題を解くためのアルゴリズムの1種で問題の条件によってはダイクストラなどの方法が早い場合があるそうです。

ベルマンフォード法の特徴は以下のようです。

最短経路問題を解くためのアルゴリズム
負数を含む場合も問題を解くことができる(ダイクストラは解けない)
負経路を含む場合(閉路が存在するときにその閉路の枝の重みの総和が負数になる)正しい計算はできないが、検出は可能

今回の問題にぴったりな感じがしますね。

アルゴリズムのコアな部分

最短経路の保管するデータ構造を初期化
各頂点に対して以下の処理を繰り返す
- 全ての枝に対して以下の処理を繰り返す
  - 枝がない場合、スキップ
  - 移動後のコストよりも低くなる場合は更新その時の枝を負数の枝にする。
  - 枝の元が訪問済みならば枝の先も負数の枝にする

今回の問題のコツ

重みを反転をすれば負経路が正経路と考えることができるので、それでinfの検出を行えば良さげな気がします。
重みの計算の値を頂点ごとに保管するデータ構造を作りそこの値を再利用する。
判定した重みを答えで反転すれば正しい答えを求めることができる。

プログラムのフローは以下のような感じです。

値の受け取り重みは正負反転
ベルマンフォード法を使って最短経路の算出
負経路(正経路)の検出
負経路がある場合
- inf
そうでない場合
- 最短経路

プログラム

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <math.h>
#include <deque>
#include <stack>
 
using namespace std;
 
typedef long long ll;
 
 
int solve() {
  ll n, m;
  const ll INF = 1145141919810;
  cin >> n >> m;
  vector<ll> a(m),b(m),c(m);
  for(ll i = 0;i < m;i++){
    cin >> a[i] >> b[i] >> c[i];
    c[i] = -c[i];
  }
  vector<ll> dist(n,INF);
  dist[0] = 0;
  // Bellman–Ford
  for(ll i = 0;i < n - 1; i++){
    for(ll j = 0;j < m;j++){
      // 最短経路値の計算
      if(dist[a[j] - 1] == INF){
        continue;
      }
      if(dist[b[j] - 1] > dist[a[j] - 1] + c[j]){
        dist[b[j] - 1] = dist[a[j] - 1] + c[j];
      }
    }
  }
  ll ans = dist[n - 1];
  vector<bool> negative(n, false);
  // 閉路の検索
  for(ll i = 0;i < n; i++) {
    for(ll j = 0;j < m; j++){
      if(dist[a[j] - 1] == INF){
        continue;
      }
 
      if(dist[b[j] - 1] > dist[a[j] - 1] + c[j]){
        negative[b[j] - 1] = true;
      }
 
      if(negative[a[j] - 1] == true){
        negative[b[j] - 1] = true;
      }
    }
  }
  if(negative[n - 1]){
    cout << "inf" << endl;
  }else{
    cout << -ans << endl;
  }
  return 0;
}
 
int main(void){
  solve();
  return 0;
}

まだ理解が曖昧な部分がある場合があるので、指摘していただけるとありがたいです。。

xlkeiの日記

ABC061 D Score Attack とベルマンフォード法

ABC061

Score Attack

アルゴリズムのコアな部分

今回の問題のコツ

プログラム