UnKoder #01 C XOR Graph

2015/04/15 (Wed) hackerrank UnKoder グラフ XOR 最小全域木 ☆

問題

日本語があります

方針

最初からつながっていない 2 頂点の間には、$1,2,4,8, \cdots $ という1ビットだけ立った整数の 重みの辺がつながっていると仮定して普通に最小全域木を求める。 2ビット以上使った辺は全て1ビット以下で実現できる。

実装

↑であってると思うのですが、なぜか通らないので他の人のコードを見てください…

~~https://www.hackerrank.com/contests/unkoder-01/leaderboard~~

UPD:

sugim さん本人から指摘されて気づいたのですが、原因は逆辺の追加し忘れでした。 (貼り付けたクラスカル法が無向グラフ専用だったのでif (u < g[u][i].dst)の部分で弾かれてしまっていました。)

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src_, int dst_, Weight weight_) :
        src(src_), dst(dst_), weight(weight_) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

struct UnionFind {
    vector<int> par;
    int cnt;
    UnionFind(int size_) : par(size_, -1), cnt(size_) { }
    bool set(int x, int y) {
        x = find(x); y = find(y);
        if (x != y) {
            if (par[y] < par[x]) swap(x, y);
            par[x] += par[y]; par[y] = x;
            cnt--;
        }
        return x != y;
    }
    bool get(int x, int y) {
        return find(x) == find(y);
    }
    int find(int x) {
        return par[x] < 0 ? x : par[x] = find(par[x]);
    }
    int size(int x) {
        return -par[find(x)];
    }
    int size() {
        return cnt;
    }
};

pair<Weight, Edges> kruskal(Graph const& g){
    int n = g.size();
    UnionFind uf(n+1);
    Edges es;
    rep(u, n) rep(i,g[u].size()) if (u < g[u][i].dst) es.push_back(g[u][i]);
    sort(all(es)); // !! INVERSE !!
    reverse(all(es));
    Weight total = 0;
    Edges res;
    for(auto const & e : es){
        if(!uf.get(e.src,e.dst)){
            res.push_back(e);
            total += e.weight;
            uf.set(e.src,e.dst);
        }
    }
    return make_pair(total,res);
}

int main(){
    int N,M;
    cin >> N >> M;
    Graph g(N);
    rep(i,M){
        int a,b;
        cin >> a >> b;
        g[a].eb(a,b,0);
        g[b].eb(b,a,0);
    }
    rep(i,N){
        int t = 1;
        while(t < N){
            if((i^t) < N) g[i].eb(i,i^t,t);
            t<<=1;
        }
    }
    auto ans = kruskal(g);
    cout << ans.first << endl;
}