SRM675 Div1 Easy TreeAndPathLength3

2015/12/15 (Tue) SRM グラフ理論 ロシアゲー

問題

問題文

同じ頂点を使わない長さ 3 のパスが $s$ 個あるような木を作ってください.$1 \leq s \leq 10000$ ですが,頂点の数は $500$ 以下でないといけません.

方針

$s$ が小さければ鎖状のグラフを構築すればいいです. ある程度大きい場合は,図のような木があったとします.この木に含まれる長さ $3$ のパスの数は $ab+b+c-1$ 個です. それが $s$ になるような $a,b,c$ を探索し,構築して返します.

fig

実装

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;
    }
};