SRM 492 div2 hard:TimeTravellingSalesman

問題解くより入力の処理の仕方に対応するのに時間かかった。
stringstream 使って getline の流れは覚えておいたほうが良いかも。

問題

TopCoder Statistics - Problem Statement

解法

最小全域木やるだけ。

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

struct edge {
    int from;
    int to;
    ll w;
    edge() {}
    edge(int f, int t, ll w) : from(f), to(t), w(w) {}
    bool operator<(const edge& rhs) const {return w < rhs.w;}
};

class TimeTravellingSalesman {
public:
    long long determineCost(int N, vector <string> roads) {
        vector<edge> G;
        UnionFind uf(N);
        string s;
        for (string t : roads) s += t;
        stringstream ss(s);
        string item;
        while (getline(ss, item, ' ')) {
            if (!item.empty()) {
                int f, t, w;
                sscanf(item.c_str(), "%d,%d,%d", &f, &t, &w);
                G.emplace_back(f, t, w);
            }
        }
        sort(G.begin(), G.end());
        ll ans = 0;
        for (edge e : G) {
            if (!uf.same(e.from, e.to)) {
                uf.unite(e.from, e.to);
                ans += e.w;
            }
        }
        for (int i = 0; i < N; i++) if (!uf.same(0, i)) return -1;
        return ans;
    }
};

多分逆に制約を小さくして N=20 とかにされたらかなり迷ったと思う(制約で惑わすのも問題作成のテクニックではあるよね)。