ある種典型?
https://community.topcoder.com/stat?c=problem_statement&pm=16248&rd=18085
問題
N*Nのグリッドが与えられる。
一部は通行不可なマスである。
それ以外のマスに対し、道路を敷きたい。
各マスにおいて、道路は隣接する通行不可でないマスのうち2つに連結していなければならない。
これを満たそうとすると、自然に道路は閉路を成す。
グリッドの状態に対し、道路の敷き方を1つ答えよ。道路は複数の閉路で構成されていてもよい。
解法
最大フローで解ける。
各セルは隣接する2セルに道路がつながっている点に着目しよう。
グリッドを市松模様状に塗り分けると、sourceから通行不可でない各白マスに容量2の辺をはり、白マスから隣接する黒マスに容量1の辺を張り、通行不可でない黒マスからsinkに容量2の辺を張ろう。
通行不可でない白マスと黒マスの数が一致するなら、その総和の分フローを流せればよいことになる。
あとはフローを復元して元の道路を求める。
template<class V> class MaxFlow_dinic { public: struct edge { int to,reve;V cap;}; static const int MV = 1100; vector<edge> E[MV]; int itr[MV],lev[MV]; void add_edge(int x,int y,V cap,bool undir=false) { E[x].push_back((edge){y,(int)E[y].size(),cap}); E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0}); } void bfs(int cur) { MINUS(lev); queue<int> q; lev[cur]=0; q.push(cur); while(q.size()) { int v=q.front(); q.pop(); ITR(e,E[v]) if(e->cap>0 && lev[e->to]<0) lev[e->to]=lev[v]+1, q.push(e->to); } } V dfs(int from,int to,V cf) { if(from==to) return cf; for(;itr[from]<E[from].size();itr[from]++) { edge* e=&E[from][itr[from]]; if(e->cap>0 && lev[from]<lev[e->to]) { V f=dfs(e->to,to,min(cf,e->cap)); if(f>0) { e->cap-=f; E[e->to][e->reve].cap += f; return f; } } } return 0; } V maxflow(int from, int to) { V fl=0,tf; while(1) { bfs(from); if(lev[to]<0) return fl; ZERO(itr); while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf; } } }; vector<int> E[31][31]; int vis[31][31]; int N; class ParkPlace { public: void dfs(int y,int x,int py,int px,string& S) { if(vis[y][x]) return; vis[y][x]=1; FORR(e,E[y][x]) { int ty=e/N; int tx=e%N; if(ty==py&&tx==px) continue; if(ty>y) S+='S'; if(ty<y) S+='N'; if(tx>x) S+='E'; if(tx<x) S+='W'; dfs(ty,tx,y,x,S); break; } } vector <string> construct(int N, vector <string> place) { ::N=N; MaxFlow_dinic<int> mf; int y,x; int C[2]={}; FOR(y,N) FOR(x,N) if(place[y][x]=='.') { C[(x+y)%2]++; if((x+y)%2==0) { mf.add_edge(1000,y*N+x,2); if(x) mf.add_edge(y*N+x,y*N+x-1,1); if(y) mf.add_edge(y*N+x,(y-1)*N+x,1); if(x+1<N) mf.add_edge(y*N+x,y*N+x+1,1); if(y+1<N) mf.add_edge(y*N+x,(y+1)*N+x,1); } else { mf.add_edge(y*N+x,1001,2); } } if(C[0]!=C[1]) return {}; int ret=mf.maxflow(1000,1001); if(ret!=C[0]*2) return {}; FOR(y,N) FOR(x,N) E[y][x].clear(), vis[y][x]=0; FOR(y,N) FOR(x,N) if((y+x)%2==0 && place[y][x]=='.') { FORR(e,mf.E[y*N+x]) { if(e.to<1000&&e.cap==0) { E[y][x].push_back(e.to); E[e.to/N][e.to%N].push_back(y*N+x); } } } vector<string> RR; FOR(y,N) FOR(x,N) if(place[y][x]=='.' && vis[y][x]==0) { string S; S=to_string(y)+" "+to_string(x)+" "; dfs(y,x,100,100,S); RR.push_back(S); } return RR; } }
まとめ
似たようなの過去にもSRMで解いた気がするんだよな…。