SRM 693 div2 easy TriangleEasy
問題概要
グラフが与えられる。そのグラフの中に三角形を作る。最小でいくつの辺を加えればできるか。
解法
まず、辺が1つもなければ、必要な最小の辺の数は3となる。次に辺がある場合を考える。u - v の辺がある場合を考える。このとき、u - x(xはvではない)辺が存在すれば、辺を加える数は1つでよくなる。同様にv - y(yはuではない)辺が存在すれば、辺を加える数も1つでよくなる。そして、x = yとなるものが存在すれば、すでに三角形はできているので、加える辺の最小数は0ということになる。
5角形の閉路検出
ミス
はじめは、dfsで探索しようと思って書いたけど、なんかうまくいかない。
コード
#include <iostream> #include <string> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) bool G[55][55]; class TriangleEasy{ public: int find(int n, vector <int> x, vector <int> y){ rep(i, 55)rep(j, 55) G[i][j] = false; for (int i = 0; i < x.size(); ++i){ int u = x[i], v = y[i]; G[u][v] = true; G[v][u] = true; } bool flag1 = false; bool flag2 = false; rep(u, n)rep(v, n){ if(u == v) continue; /* w / \ u - v */ if(G[u][v]){//u - vに辺がある rep(w, n){ if(u == w || v == w) continue; if(G[w][u] && G[w][v]) flag2 = true; else if(G[w][u] || G[w][u]) flag1 = true; } } } if(x.size() == 0 || y.size() == 0) return 3; else if(flag2) return 0; else if(flag1) return 1; else return 2; } };