SRM 687 div1 med: AllGraphCuts
問題
TopCoder Statistics - Problem Statement
頂点のペア (i, j) に対して, 「頂点 i と頂点 j に対する最小カットは x[i*n+j]」という条件を表す n*n 要素の配列 x が与えられる。
この条件を満たす重みつき無向グラフがあるならそれを出力し, 存在しないなら {-1} を出力せよ。
解法
理由がよくわからないんですが,
- 重みの大きい順に辺をソート
- 重みの大きい順に辺(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; } };