SRM675 Div1 Easy TreeAndPathLength3
問題
同じ頂点を使わない長さ 3 のパスが $s$ 個あるような木を作ってください.$1 \leq s \leq 10000$ ですが,頂点の数は $500$ 以下でないといけません.
方針
$s$ が小さければ鎖状のグラフを構築すればいいです. ある程度大きい場合は,図のような木があったとします.この木に含まれる長さ $3$ のパスの数は $ab+b+c-1$ 個です. それが $s$ になるような $a,b,c$ を探索し,構築して返します.
実装
class TreeAndPathLength3 {
public:
vector <int> construct(int s) {
if(s <= 6) return generate(s);
for(int a = 1; a <= 500; a++){
for(int b = 1; b <= 500; b++){
for(int c = 1; c <= 500; c++){
int x = a*b+b+c-1;
if(x == s && a+b+c+2 <= 500){
return generate(a,b,c);
}
}
}
}
throw "";
}
void add(vector<int> &v, int a, int b){
v.eb(a); v.eb(b);
}
vector<int> generate(int s){
vector<int> v;
rep(i,s+2) add(v,i,i+1);
return v;
}
vector<int> generate(int a, int b, int c){
dump(a,b,c);
vector<int> v;
rep(i,a) add(v,i,a+b+c);
rep(i,b) add(v,a+i,a+b+c+1);
rep(i,c) add(v,a+b-1+i,a+b+i);
add(v,a+b+c,a+b+c+1);
return v;
}
};