SRM 658 div1 easy: OddEvenTree

問題概要

N頂点(頂点0～N-1)の木の距離行列xが与えられる。
0 <= i, j <= N-1を満たす全ての(i, j)組について
x[i][j] = 'O'ならば頂点(i, j)間が奇数長
x[i][j] = 'E'ならば頂点(i, j)間が偶数長
が成り立つような、木は存在するだろうか。
存在しなければ{-1}を返し、存在すれば、そのような木を一つ出力せよ。

解法

木が存在するためには、以下の条件を全て満たす必要がある。
・xが対称行列
・全てのiについて、x[i][i] == 'E'
・任意の3頂点A, B, Cについて、AB間の距離 + BC間の距離 + CA間の距離が偶数
・一つ以上'O'が存在
なお、これは十分条件ではない（テストケース88は、これらすべてを満たすが、{-1}を返すべきケース）

上の条件をすべて満たしたとき、木の構築をする。
木の構築は、以下の貪欲アルゴリズムで行い、全部つなげなければ{-1}を返すようにしたら通った。
・頂点0を接続済み頂点にする。他の頂点は「接続済み頂点」ではない。
・全ての頂点を「接続済み頂点」にするか、つなげなくなるまで以下を繰り返す。
　・「接続済み頂点A」と「接続済みでない頂点B」を見つけたら、頂点AとBを結ぶ。
　・見つからなければ、{-1}を返す。

・このアルゴリズムを使って木を構築したとき、条件を満たさない木が出来たり、条件を満たす木が存在するのに{-1}を返したり しなかった。理由は良くわからない。

//必要条件だけで枝刈り＆条件を満たしたらすぐにつなぐ、という嘘っぽいあれ。
//木の構築中に矛盾が生じたらfalseでも良かったけど、見落としがあると不味いので。
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class OddEvenTree{
    public:
    vector<int> False(){
        vector<int> ret;
        ret.push_back(-1);
        return ret;
    }
    vector<int> getTree(vector<string> x)
    {
        int i, j, k;
        int n = x.size();
        int Ecnt = 0;
        
        for( i = 0; i < n; i++ ){
            for( j = 0; j < n; j++ ){
                if( x[i][j] != x[j][i] )
                    return False();
                if( i == j && x[i][i] == 'O' )
                    return False();
                Ecnt += (x[i][j] == 'E');
            }
        }
        if( Ecnt == 0 ){
            return False();
        }
        for( i = 0; i < n; i++ ){
            for( j = 0; j < n; j++ ){
                for( k = 0; k < n; k++ ){
                    int d = (x[i][j] == 'O') + (x[j][k] == 'O') + (x[k][i] == 'O');
                    if( d % 2 == 1 )
                        return False();
                }
            }
        }
        
        //木の構築(エラーは検出済みなので、これで構築できなかったら最適な構築ではない)
        //ばばーん
        //(貪欲に構築しているため、条件を満たさない木が出来るかもしれない…)
        bool used[50] = {false};
        int sz = 1;
        vector<int> ans;
        
        used[0] = true;
        
        while( sz < n ){
            bool okflag = false;
            for( i = 0; i < n; i++ ){
                for( j = 0; j < n; j++ ){
                    if( used[i] && !used[j] && x[i][j] == 'O' ){
                        used[j] = true;
                        ans.push_back(i); ans.push_back(j);
                        okflag = true;
                        sz++;
                    }
                }
            }
            if( !okflag ){
                return False();
            }
        }
        return ans;
    }
};

提出コードのコメントがひどい