AGC039-B 死亡

死亡

前回のA問題の続きです。
問題URL  

 B - Graph Partition

問題文が分かりにくいので図にしました。

これをこうしたい

最近機械学習系をやっているので図がニューラルネットワークっぽくなりましたw

ニューラルネットワークの図(引用http://starpentagon.net/analytics/neural_network_structure/)

解法

上の状態にするには二部グラフであるかを判定すればよくなる。 二部グラフについてはゴリラジオ体操のあの霊長類さんのブログに詳しくのってます。

二部グラフ

で、できるかどうかを判定した後、頂点から頂点へ一番長いパスの長さ(直径というらしい)を求めて+1すれば答えになります。
bfsでもできるらしいですが、私は卍warshall_floyd法卍が好きなのでそちらにしました。(実装も軽いので)

ソースコード

提出 #7878405
(こういうソースコードでテンプレベタベタは好きじゃないので頑張って書いてます。褒めて。)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define MAX 1<<29
typedef long long ll;


vector<vector<ll>> g;
vector<ll> depth;
bool flag = false;

void dfs(int pos, int dep){
  if(depth[pos] >= 0) {
      if(depth[pos] != dep) flag = true;
      return;
  }
  depth[pos] = dep;
  for(auto x:g[pos]) dfs(x,dep^1);
}

int main(){
  ll n;cin>>n;
  vector<string> s(n);
  rep(i,n) cin>>s[i];
  vector<vector<ll>> dist(n, vector<ll>(n, MAX));
  g.resize(n);
  rep(i,n){
    rep(j,n) if(s[i][j] == '1') {
        g[i].push_back(j);
        dist[i][j] = 1;
    }
  }
  //二部グラフ判定
  depth.resize(n, 0);
  rep(i,n) depth[i] = -1;
  dfs(0,0);
  if(flag){
      puts("-1");
      return 0;
  }
  //warshall_floyd法
  rep(i,n) dist[i][i]=0;
  rep(k,n)rep(i,n)rep(j,n) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
  ll ans=0;
  rep(i,n) ans = max(ans,*max_element(dist[i].begin(),dist[i].end()));
  cout << ans + 1 << endl;
  return 0;
}
  

感想

;max_element()なる便利関数を初めて知りました。便利。
高専プロコンまでデスマーチ頑張ります。