mayoko’s diary

プロコンとかいろいろ。

SRM 687 div1 med: AllGraphCuts

問題

TopCoder Statistics - Problem Statement

頂点のペア (i, j) に対して, 「頂点 i と頂点 j に対する最小カットは x[i*n+j]」という条件を表す n*n 要素の配列 x が与えられる。
この条件を満たす重みつき無向グラフがあるならそれを出力し, 存在しないなら {-1} を出力せよ。

解法

理由がよくわからないんですが,

  1. 重みの大きい順に辺をソート
  2. 重みの大きい順に辺(i, j, cost)を見ていき, i, j がすでに連結なら最小カット(i から j に向かうとき通る辺のコストの最小値)が cost でないなら -1 を返す。そうでないなら i->j に重み cost の辺を貼る

でやったら解けました。あとで説明できればします。

const int INF = 1e9;
int in[55][55];

struct Edge {
    int u, v;
    int cost;
    Edge () {}
    Edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}
    bool operator<(const Edge& rhs) const {return cost < rhs.cost;}
};

void dfs(int p, int v, int to, int sofar, int& cut, const vector<vector<pii> >& w) {
    if (v == to) {
        cut = sofar;
        return;
    }
    for (pii e : w[v]) {
        if (e.first == p) continue;
        dfs(v, e.first, to, min(sofar, e.second), cut, w);
    }
}

class AllGraphCuts {
public:
    vector <int> findGraph(vector <int> x) {
        const vector<int> no = {-1};
        int n2 = x.size();
        int n = 0;
        while (n*n < n2) n++;
        assert(n*n == n2);
        vector<Edge> es;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            in[i][j] = x[i*n+j];
            if (i != j) es.emplace_back(i, j, in[i][j]);
        }
        for (int i = 0; i < n; i++) if (in[i][i] != 0) return no;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (in[i][j] != in[j][i]) return no;
        }
        vector<Edge> write;
        vector<vector<pii> > w(n);
        sort(es.rbegin(), es.rend());
        for (Edge e : es) {
            int cut = -1;
            dfs(-1, e.v, e.u, INF, cut, w);
            if (cut == -1) {
                w[e.v].emplace_back(e.u, e.cost);
                w[e.u].emplace_back(e.v, e.cost);
                write.push_back(e);
            } else if (e.cost != cut) return no;
        }
        vector<int> ans;
        for (Edge e : write) {
            ans.push_back(n*n*e.cost+n*e.v+e.u);
        }
        return ans;
    }
};