SRM 228 DIV1 Hard Loopy
問題
略。あまりわかってない
解答
Practice Roomのiwiさんの解答を参考にした。
"entry"ステートメントとループの末尾を全探索する。
そしてうまい感じでdfsする感じの感じ。わかってない。
末尾からグラフを逆にentryに達するまで見ていき、デッドコードでないならentryから到達できる必要がある。
何故なら、entryから到達できないならループには入れないが、(そこ→末尾)というふうに、ループ外からループ内に入ることになるため。
entryから到達できるなら、ループに含まれないといけない。末尾からループ内に入るから。
それで到達できた所を数えればいい。
コメント
うまいdfsの感じ、苦手だな。
そもそも問題もあまり良くわかっていない感じもあって。
どうでもいいけど、ttp://d.hatena.ne.jp/chokudai_pre/20090126/1232952987 にあるように、過去に日本のみんなで練習したことのあるPractice Roomのようだ。
コード
#include <string> #include <vector> #include <algorithm> #include <sstream> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f using namespace std; bool g[55][55], wf[55][55], ret[55], path[55]; bool vis[55]; struct Loopy { int n; bool dfs(int i, int entry) { if(vis[i]) return true; if(!wf[0][i]) return true; vis[i] = true; if(i == 0 || !wf[entry][i]) return false; bool r = true; rep(j, n) if(g[j][i]) r &= dfs(j, entry); return r; } int minLoop(vector <string> code) { n = code.size(); mset(g, 0), mset(ret, 0), mset(path, 0), mset(wf, 0); rep(i, n) { if(code[i][0] == 'I') { stringstream ss(code[i]); int x, y; string t; ss >> t >> x >> t >> y; g[i][x] = g[i][y] = true; }else ret[i] = true; } rep(i, n) rep(j, n) wf[i][j] = g[i][j]; rep(k, n) rep(i, n) rep(j, n) wf[i][j] |= wf[i][k] && wf[k][j]; rep(i, n) rep(j, n) path[i] |= wf[i][j] && ret[j]; int r = INF; rep(entry, n) if(wf[0][entry] && path[entry]) { if(g[entry][entry]) { r = min(r, 1); continue; } rep(last, n) if(wf[entry][last] && g[last][entry]) { mset(vis, 0); vis[entry] = true; if(!dfs(last, entry)) continue; r = min(r, count(vis, vis+n, true)); } } return r == INF ? 0 : r; } };