SRM 692 Div1 easy : HardProof

問題概要 :

任意の２点間に辺があるような重み付き有向グラフが隣接行列Dとして与えられる

このグラフはn個の頂点から成り、各頂点には0から順にn-1まで番号が割り振られている

全ての頂点を少なくとも１回以上訪れるような閉路について考えたとき、

この閉路に含まれる辺の重みの最大値と最小値の差の最小値を求めよ

解法 :

強連結成分分解 + 二分探索で解いた

まず、閉路中に存在する辺の重みの最大値と最小値を決める

ただし愚直に最大値と最小値を決めてしまうと全ての辺の重みが異なる場合にTLEする

( 最大値、最小値の取りうる数はそれぞれ2500なので総当たりすると2500 * 2500, その後の処理に2500かかるので 2500^3 で TLE する　その後の処理をlogくらいに抑えれればTLEしないけど)

そこで、最小値だけを総当たりで決める

最小値が決まったとき、最小値以上の最大値の最小値は二分探索により求めることができる

このとき、与えられたグラフの中から辺の重みが最小値未満もしくは最大値より大きいものを除いたグラフについて考える

このグラフ中に、全ての頂点を少なくとも１回以上訪れるような閉路が存在すれば良い

ここでは既に余計な辺を削除してあるので、このグラフ中に平路が存在するかどうかを判定すれば良い

これはグラフ中に橋が存在するかどうかで判断できる

( 橋とは？ 参考 : http://hos.ac/slides/20110504_graph.pdf

橋 : グラフ中に存在する辺のうち、それを取るとグラフの連結成分数が増えるようなもののこと)

今回グラフは有向グラフなので、強連結成分の数が１つかどうかで判断できる

強連結成分の数が２以上なら、異なる２つの強連結成分同士を結ぶような辺が橋になるからである

V,Eをそれぞれグラフの頂点集合、辺集合とすると計算量は
閉路中の辺の重みの最小値を総当たりするので |V| = 2500
二分探索で最大値を決定するので log2(|V|) = log2(2500) ≒11.287712379549449
強連結成分分解 |V| + |E| = 50 + 2500
O( |V| * log(|V|) * (|V|+|E|) )
最悪ケースでは 2500 * log2(2500) * 2550 ≒ 70548202.37218405となる
10^8以下なので十分１秒以内に終わる

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

const int IINF = INT_MAX;

int V;
int mat[51][51];
bool visited[51];

class HardProof {
public:

  int lower, upper;

  vector<vector<int> > G,rG;
  vector<bool> used;
  vector<int> cmp,vs;

  void add_edge(int s,int t){
    G[s].push_back(t);
    rG[t].push_back(s);
  }

  void dfs(int v){
    used[v] = true;
    for(int i=0;i<(int)G[v].size();i++) if( !used[G[v][i]] ) dfs(G[v][i]);
    vs.push_back(v);
  }

  void rdfs(int v,int k){
    used[v] = true;
    cmp[v] = k;
    for(int i=0;i<(int)rG[v].size();i++) if( !used[rG[v][i]] ) rdfs(rG[v][i],k);
  }

  int scc(){
    rep(i,V) used[i] = false;
    vs.clear();
    rep(v,V) if( !used[v] ) dfs(v);
    rep(i,V) used[i] = false;
    int k = 0;
    for(int i=vs.size()-1;i>=0;i--) if( !used[vs[i]] ) rdfs(vs[i],k++);
    return k;
  }

  bool check() {
    if( lower > upper ) return false;
    G.clear(), rG.clear(), cmp.clear(), used.clear();
    G.resize(V,vector<int>()), rG.resize(V,vector<int>()),cmp.resize(V), used.resize(V);
    rep(i,V) {
      rep(j,V) if( i != j && ( lower <= mat[i][j] && mat[i][j] <= upper ) ) {
	add_edge(i,j);
      }
    }
    return scc() == 1;
  }

  int minimumCost(vector <int> D) {
    V = sqrt((int)D.size());
    if( V == 1 ) return 0;
    rep(i,V) rep(j,V) mat[i][j] = D[i*V+j];
    vector<int> lowers;
    rep(i,V) rep(j,V) lowers.push_back(mat[i][j]);
    sort(lowers.begin(),lowers.end());
    lowers.erase(unique(lowers.begin(),lowers.end()),lowers.end());
    int mini = IINF;
    rep(i,(int)lowers.size()) {
      lower = lowers[i];
      int L = 0, R = ((int)lowers.size());
      while( L + 1 < R ) {
	int M = ( L + R ) / 2;
	upper = lowers[M];
	if( check() ) {
	  R = M;
	  mini = min(mini,upper-lower);
	} else {
	  L = M;
	}
      }
    }
    return mini;
  }
};