ABC022 C Blue Bird

問題概要

1~Nの番号付けされた家がある。道も1~Mの番号付けされている。それぞれの道は、家uと家vを距離lでつなぐ。
家1からスタートして同じ道を二度以上通らずに、家1以外の家を少なくとも1軒を経由して家1に戻るための最短経路を求める。ただし、そのような経路がない場合は-1を出力する。

制約

• 3 ≤ N ≤ 300
• 3 ≤ M ≤ N(N-1)/2
• 1 ≤ u,v ≤ N
• 1 ≤ l ≤ 10^5

解法1

ワーシャルフロイド。
まず、はじめに家1と道で繋がれている家とその距離を列挙する。
それらの道を除いてワーシャルフロイドする。
最後に、二重ループで1 ->x -> y -> 1となる(x,y)の組を全て試し最小をとる。
(1 -> x と y -> 1 の距離は入力で与えられたもの。x -> y 間の距離はワーシャルフロイドで求めている。)
もしその最小値が更新されないなら経路が存在しない。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1e9
 
int main(){
  int N,M,d[301][301],a,b,c,f[301][301];
  vector<int> e;
  cin >> N >> M;
  fill(d[0],d[0]+301*301,INF);
  fill(f[0],f[0]+301*301,INF);
  for(int i = 0 ; i < 301 ; i++){
    d[i][i] = 0;
  }
  for(int i = 0 ; i < M ; i++){
    cin >> a >> b >> c;
    a--; b--;
    if(a == 0){
      f[a][b] = f[b][a] = c;
      e.push_back(b);
    }else{
      d[a][b] = d[b][a] = c;
    }
  }
  for(int k = 0 ; k < N ; k++){
    for(int i = 0 ; i < N ; i++){
      for(int j = 0 ; j < N ; j++){
        d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }
 
  int res = INF;
  for(int i = 0 ; i < (int)e.size() ; i++){
    for(int j = i+1 ; j < (int)e.size() ; j++){
      res = min(res,f[0][e[i]]+d[e[i]][e[j]]+f[e[j]][0]);
    }
  }
  cout << (res == INF ? -1 : res) << endl;
  return 0;
}

解法2

最小費用流。
uとv間にcostがcでcapが1のエッジを張る。
家1から家2,3,…,Nのすべてについて流量2で流し、その最小値をとっていく。

ちなみに最小費用流はダイクストラを用いる方でなければTLEした。
また、この解法は蟻本のP214の問題に似ている。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_V 301
#define INF (1<<29)
typedef pair<int,int> P;
 
struct edge{ int to,cap,cost,rev; };
 
int V,h[MAX_V];
vector<edge> G[MAX_V],tmp[MAX_V];
int dist[MAX_V],prevv[MAX_V],preve[MAX_V];
 
void add_edge(int from,int to,int cap,int cost){
  G[from].push_back((edge){to,cap,cost,G[to].size()});
  G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}
 
int min_cost_flow(int s,int t,int f){
  int res = 0;
  fill(h, h + V, 0);
  while(f > 0){
    priority_queue<P, vector<P>, greater<P> > Q;
    fill(dist, dist + V, INF);
    dist[s] = 0;
    Q.push(P(0,s));
    while(!Q.empty()){
      P p = Q.top(); Q.pop();
      int v = p.second;
      if(dist[v] < p.first){ continue; }
      for(int i = 0 ; i < (int)G[v].size() ; i++){
        edge &e = G[v][i];
        if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
          dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          Q.push(P(dist[e.to],e.to));
        }
      }
    }
    if(dist[t] == INF){ return -1; }
    
    for(int v = 0 ; v < V ; v++){
      h[v] += dist[v];
    }
    
    int d = f;
    for(int v = t ; v != s ; v = prevv[v]){
      d = min(d,G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res += d*h[t];
    for(int v = t ; v != s ; v = prevv[v]){
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}
 
int main(){
  int N,M,a,b,c;
  cin >> N >> M; V = N;
  for(int i = 0 ; i < M ; i++){
    cin >> a >> b >> c; a--; b--;
    add_edge(a,b,1,c);
    add_edge(b,a,1,c);
  }
  int res = INF;
  for(int i = 1 ; i < N ; i++){
    for(int j = 0 ; j < N ; j++){
      tmp[j] = G[j];
    }
    int x = min_cost_flow(0,i,2);
    if(x >= 0){ res = min(res,x); }
    for(int j = 0 ; j < N ; j++){
      G[j] = tmp[j];
    }
  }
  cout << (res == INF ? -1 : res) << endl;
  return 0;
}