Euldernaの競技プログラミングメモ

主に気になった問題やライブラリの確認に使った問題を示します。

ICPC2017 国内予選 G問題(Go around the Labyrinth/迷宮を一周) 解説

前書き

ICPC2017年の国内予選G問題のネタバレ記事です。

ちなみに実際に本番では通せてないですが、あと10分あれば間違いなく通せてたという感じの人が書いています。

問題概要

二次元の迷路が与えられて、同じマスを二度行かないという制約の下、迷路の左上から左下・右下・右上を巡って左上に戻れるかという問題。

講評

実際には右手法で貪欲的に迷路を解いていくやり方で解いたチームが多かったようです。(講評の後半部分)

ここでは講評の前半で紹介されている最大流を用いた解法を扱います。

解法

探索書くのダルいと思います。そうするとうまくフローに逃げれないかと思います。経路の存在性は最大流アルゴリズムが典型なので、そこから考えます。(経路の存在=最小カットが1以上みたいな考察から始まります)

そうすると始点から各点までいく最大流(最小カット)が2であることが、少なくとも必要条件なのが分かります。

ここから反例になるようなものを考えると、必ずループのどこかで共有点が存在するので不可能です。

これで各点までの最大流が2であることが必要十分なことが分かります。(これは少し嘘)

このことは右手法で解が得られる根拠になっています。

この発想でプログラムするとサンプルの2が合わなくて悲しい気持ちになります。

ここで各マスに流入するのは必ず1であることに気がつけば、ノードの持ち方を工夫すれば解けますね。(本当は考察の段階で気がつきましょう)

つまり一つのノードを次のように持てばよいですね。

f:id:Eulderna:20171229204739p:plain

時間計算量はO(盤面のサイズ)で十分高速です。

コード

半年前の緑時代&&ICPCルールでのタイムアタック時のコードなので汚いです。参考までに。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
 
 
#define REP(i,n) for(int i=0;i<(n);i++)
#define pb push_back
 
using namespace std;
 
const int INF = 1000000000;
 
#define MAX_V 5010
struct Edge{int to,cap,rev;};
typedef vector<Edge> Edges;
Edges G[MAX_V];
bool used[MAX_V];//for DFS
 
void add_Edge(int from,int to,int cap){
  G[from].pb((Edge){to,cap,G[to].size()});
  G[to].pb((Edge){from,0,G[from].size()-1});
}
 
int dfs(int v,int t,int f){
  if(v == t) return f;
  used[v] = true;
  REP(i,G[v].size()){
    Edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d > 0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}
 
int Ford_Fulkerson(int s,int t){
  int flow = 0;
  while(1){
    memset(used,0,sizeof(used));
    int f = dfs(s,t,INF);
    if(f == 0) return flow; //max flow
    flow += f;
  }
}
int main(){
  int n,m;
  while(cin >> n >> m,n){
    REP(i,5010)
      G[i].clear();
    vector<string> s(n);
    REP(i,n){
      cin >> s[i];
    }
    REP(i,n){
      REP(j,m){
        add_Edge(i*m+j,i*m+j+2501,1);
        if(s[i][j] == '.'){
          if(s[i][j+1] == '.'&& j != m-1){
            add_Edge(i*m+j+2501,i*m+j+1,1);
            add_Edge(i*m+j+1+2501,i*m+j,1);
 
          }
          if(i != n-1){
            if(s[i+1][j] == '.'){
              add_Edge(i*m+j+2501,(i+1)*m+j,1);
              add_Edge((i+1)*m+j+2501,i*m+j,1);
 
            }
          }
        }
      }
    }
    Edges tG[5010];
    REP(i,5010)
      tG[i] = G[i];
     
    string ans = "NO";
    if(Ford_Fulkerson(2501,m-1) == 2){
      REP(i,5010)
        G[i] = tG[i];
      if(Ford_Fulkerson(2501,n*m-1) == 2){
        REP(i,5010)
          G[i] = tG[i];
        if(Ford_Fulkerson(2501,n*m-m) == 2)
          ans = "YES";
      }
    }
    cout << ans << endl;
  }
  return 0;
}

結論

フローは神。

TLにたまたまこの問題について流れてきたので書きました。

Maximumの人はwikiに上げてある部内向け解説の方が分かりやすいのでそっちを見て。