SRM 653 div1 med:Singing
答えみて書いただけでまだあんまり納得できてない・・・
問題:TopCoder Statistics - Problem Statement
解法:yosupoさんのページを参考にしました。
最小カットについて - よすぽの日記
このページでは,
・頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない
・必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する
・「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある
・罰金の最小値は?
という問題は
・「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る
・SからTに最大流
・流せた量が答え
とすることで解けるとしています。今のところこれが正しいことを納得できてないのですが,これが正しいとしてグラフを作ると次のようにすればOKです。
頂点S,T,(1,...,N)を作る。
Aliceが担当する音階を青,Bobが担当する音階を赤とすると,条件より
Bobは1〜low-1の音階を担当しなければならないが,これはSからi(i=1〜low-1)へ容量∞の辺を貼ることで解決。
Aliceはhigh+1〜Nの音階を担当するのも,i(i=high+1〜N)からTへ容量∞の辺を貼ることで解決。
あとはBobとAliceが入れ替わったところで「もしAliceとBobで担当が入れ替わったら」コストが1かからなければならないが,これは制約として「pitch[i]が赤でpitch[i+1]が青なら1の罰金がかかる」と「pitch[i+1]が赤でpitch[i]が青なら1の罰金がかかる」というものであるので,両方向の辺を貼ればOK。
ということで問題を解くことができます。
この問題なんかとっつきにくいんですが,なにが問題を難しく感じさせているのかはわかった気がします。(今まで解いた最大フロー/最小カット問題が少なすぎるからかもしれませんが)よくある最小カット問題のグラフの構成は,制約条件の「選択肢」(例えばよくある仕事の割り当て二部マッチング問題の場合は「どのコンピュータが,どの仕事を担当するか」という選択肢)は辺の選び方に委ねられています。一方で,この問題の場合は選択肢(今回の場合は「音階をAliceとBobどちらが担当するか」)は頂点の方に委ねられています。そこがおそらくとっつきにくい方法であり,そこを見事に解決するのがyosupoさんの解法だったようです。
以下ソースコード
// max_flow const int MAX_V = 2002; const int INF = 1e6; class FordFulkerson { public: struct edge { int to; int cap; int rev; edge() {} edge(int t, int c, int r) : to(t), cap(c), rev(r) {} }; vector<edge> G[MAX_V]; void add_edge(int from, int to, int cap) { G[from].push_back(edge(to, cap, G[to].size())); G[to].push_back(edge(from, 0, G[from].size() - 1)); } int max_flow(int s, int t) { int flow = 0; while (1) { for (int i = 0; i < MAX_V; i++) used[i] = false; int f = dfs(s, t, INF); if (f == 0) return flow; flow += f; } } void clear() { for (int i = 0; i < MAX_V; i++) G[i].clear(); } private: int dfs(int v, int t, int f) { if (v == t) return f; used[v] = true; for (int i = 0; i < G[v].size(); i++) { edge &e = G[v][i]; if (!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(e.cap, f)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } bool used[MAX_V]; }; FordFulkerson ff; class Singing { public: int solve(int N, int low, int high, vector <int> pitch) { ff.clear(); int s = 0, t = N+1; for (int i = 0; i < low; i++) ff.add_edge(s, i, INF); for (int i = high+1; i <= N; i++) ff.add_edge(i, t, INF); int n = pitch.size(); for (int i = 0; i < n-1; i++) { if (pitch[i] != pitch[i+1]) { ff.add_edge(pitch[i], pitch[i+1], 1); ff.add_edge(pitch[i+1], pitch[i], 1); } } return ff.max_flow(s, t); } }