需要供給を考え、さらに最小流量制約もある最小費用フロー!!!
問題概要
左頂点数 、右頂点数 、辺数 の二部グラフが与えられる。各頂点は「赤」または「青」または「白」に塗られている。
さて、各辺は最初は白色である。そのうちの何本かを「赤」や「青」に塗って以下の条件を満たすようにしたい。
- どの「赤」の頂点についても、その頂点に接続している赤辺の本数が、青辺の本数よりも多い
- どの「青」の頂点についても、その頂点に接続している青辺の本数が、赤辺の本数よりも多い
- 「白」の頂点についてはそのような制約はない
赤く塗るコストは 1 本あたり で、青く塗るコストは 1 本あたり である。最小コストで実現する方法を求めよ (復元もせよ)。
制約
考えたこと
各辺について
- 赤色に塗る: 左から右へ 1 のフローを流す (左から右向きにコスト の辺)
- 青色に塗る: 右から左へ 1 のフローを流す (右から左向きにコスト の辺)
という風に考えてみる。そうすると条件は
- 左側の赤頂点: 流量が +1 以上のソース点
- 左側の青頂点: 流量が -1 以上のシンク点
- 左側の白頂点: 流量任意
- 右側の赤頂点: 流量が -1 以上のシンク点
- 右側の青頂点: 流量が +1 以上のソース点
- 右側の白頂点: 流量任意
という需要供給を満たすような最小費用流を求める、という問題になる。需要供給付き最小費用流の求め方は、
- ソースに対応するスーパーノード を作って、流量 のソース点 に対しては、 から へ容量 の辺を張る
- シンクに対応するスーパーノード を作って、流量 のシンク点 に対しては、 から へ容量 の辺を張る
としたグラフ上で、 から への流量 の最小費用流を求めればよい。今回は、需要供給量が「下限制約付き」なので、それに関する対策も行う。ひとまず、上記と同じように
- ソース点については、 から下限容量 1 の辺を張る
- シンク点については、 へと下限容量 1 の辺を張る
という風にしておく。また流量任意の頂点 に対しては、
- から へ上限容量 の辺を張る
- から へ上限容量 の辺を張る
としておく。さらに、下限制約さえ満たせば から への流量は自由なので、 から へ上限容量 の辺を張る。こうして得られたグラフで、最小費用循環流を求める問題とみなすことができる。次に、下限容量付きの辺を処理する。
下限制約付きフローの考え方
下限制約付きフローの考え方はいたってシンプルで、
- その分の流量だけあらかじめ流してしまう
- 上限制約の値をその分だけ減らす (今回は上限制約は なので変化なし)
という風にする。あらかじめ流したことで発生する需要供給についてはまた改めて補正する。
辺 について、下限流量制約 がついているとき、 を流してしまったことにする。このとき
- は のソース点
- は のシンク点
となるので、それに対応するスーパーノードを用意して対応する
という感じ。今回結局、2 組のスーパーノード を用意して、以下のようにしたグラフにおいて、 から へと、流量 (「赤」と「青」の頂点の個数の合計値) の最小費用流を求めれば OK。
- 下限流量 1 のソース点となった頂点 (左の赤と右の青) に対しては
- には容量 の辺を張る
- から へ、容量 の辺を張る
- から へ、容量 の辺を張る (最後にまとめる)
- 下限流量 1 のシンク点となった頂点 (左の青と右の赤) に対しては
- には容量 の辺を張る
- から へ、容量 の辺を張る
- から へ、容量 の辺を張る (最後にまとめる)
- 流量任意の頂点 (左右の白) に対しては
- から へ、容量 の辺を張る
- から へ、容量 の辺を張る
- 左側頂点 と右側頂点 からなる辺については、
- から へは、容量 、コスト の辺を張る
- から へは、容量 、コスト の辺を張る
- 最後に、 から へ容量 の辺を張る
#include <iostream> #include <vector> #include <queue> #include <map> using namespace std; #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl // edge class (for network-flow) template<class FLOWTYPE, class COSTTYPE> struct Edge { int rev, from, to, id; FLOWTYPE cap, icap; COSTTYPE cost; Edge(int r, int f, int t, FLOWTYPE ca, COSTTYPE co, int id = -1) : rev(r), from(f), to(t), cap(ca), icap(ca), cost(co), id(id) {} friend ostream& operator << (ostream& s, const Edge& E) { if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ',' << E.cost << ')'; else return s; } }; // graph class (for network-flow) template<class FLOWTYPE, class COSTTYPE> struct Graph { vector<vector<Edge<FLOWTYPE, COSTTYPE> > > list; Graph(int n = 0) : list(n) { } void init(int n = 0) { list.clear(); list.resize(n); } void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; } inline vector<Edge<FLOWTYPE, COSTTYPE> >& operator [] (int i) { return list[i]; } inline const size_t size() const { return list.size(); } inline Edge<FLOWTYPE, COSTTYPE> &redge(const Edge<FLOWTYPE, COSTTYPE> &e) { if (e.from != e.to) return list[e.to][e.rev]; else return list[e.to][e.rev + 1]; } void addedge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) { list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id)); list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, 0, -cost)); } void add_undirected_edge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) { list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id)); list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, cap, cost, id)); } friend ostream& operator << (ostream& s, const Graph& G) { s << endl; for (int i = 0; i < G.size(); ++i) { s << i << ":"; for (auto e : G.list[i]) s << " " << e; s << endl; } return s; } }; // min-cost flow (primal-dual) template<class FLOWTYPE, class COSTTYPE> COSTTYPE MinCostFlow(Graph<FLOWTYPE, COSTTYPE> &G, int s, int t, FLOWTYPE f) { int n = (int)G.size(); vector<COSTTYPE> pot(n, 0), dist(n, -1); vector<int> prevv(n), preve(n); COSTTYPE res = 0; while (f > 0) { priority_queue<pair<COSTTYPE,int>, vector<pair<COSTTYPE,int> >, greater<pair<COSTTYPE,int> > > que; dist.assign(n, -1); dist[s] = 0; que.push(make_pair(0,s)); while(!que.empty()) { pair<COSTTYPE,int> p = que.top(); que.pop(); int v = p.second; if (dist[v] < p.first) continue; for (int i = 0; i < G[v].size(); ++i) { auto e = G[v][i]; if (e.cap > 0 && (dist[e.to] < 0 || dist[e.to] > dist[v] + e.cost + pot[v] - pot[e.to])) { dist[e.to] = dist[v] + e.cost + pot[v] - pot[e.to]; prevv[e.to] = v; preve[e.to] = i; que.push(make_pair(dist[e.to], e.to)); } } } if (dist[t] < 0) return -1; for (int v = 0; v < n; ++v) pot[v] += dist[v]; FLOWTYPE d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += pot[t] * d; for (int v = t; v != s; v = prevv[v]) { Edge<FLOWTYPE,COSTTYPE> &e = G[prevv[v]][preve[v]]; Edge<FLOWTYPE,COSTTYPE> &re = G.redge(e); e.cap -= d; re.cap += d; } } return res; } int main() { int N1, N2, M; long long r, b; cin >> N1 >> N2 >> M >> r >> b; string ls, rs; cin >> ls >> rs; const long long INF = 1<<29; Graph<long long, long long> G(N1 + N2 + 4); int s = N1 + N2, t = N1 + N2 + 1, ss = N1 + N2 + 2, tt = N1 + N2 + 3; long long nS = 0, nT = 0; for (int v = 0; v < N1; ++v) { if (ls[v] == 'R') { ++nS; G.addedge(s, v, INF, 0); G.addedge(ss, v, 1, 0); } else if (ls[v] == 'B') { ++nT; G.addedge(v, t, INF, 0); G.addedge(v, tt, 1, 0); } else { G.addedge(s, v, INF, 0); G.addedge(v, t, INF, 0); } } for (int v = 0; v < N2; ++v) { if (rs[v] == 'B') { ++nS; G.addedge(s, v+N1, INF, 0); G.addedge(ss, v+N1, 1, 0); } else if (rs[v] == 'R') { ++nT; G.addedge(v+N1, t, INF, 0); G.addedge(v+N1, tt, 1, 0); } else { G.addedge(s, v+N1, INF, 0); G.addedge(v+N1, t, INF, 0); } } G.addedge(s, tt, nS, 0); G.addedge(ss, t, nT, 0); for (int i = 0; i < M; ++i) { int x, y; cin >> x >> y; --x, --y; G.addedge(x, y+N1, 1, r, i); G.addedge(y+N1, x, 1, b, i); } G.addedge(t, s, INF, 0); auto res = MinCostFlow(G, ss, tt, nS + nT); cout << res << endl; if (res == -1) return 0; string ans(M, 'U'); for (int v = 0; v < N1; ++v) { for (auto e : G[v]) { if (e.id == -1) continue; if (e.cap == 0 && e.icap == 1) ans[e.id] = 'R'; } } for (int v = 0; v < N2; ++v) { for (auto e : G[v+N1]) { if (e.id == -1) continue; if (e.cap == 0 && e.icap == 1) ans[e.id] = 'B'; } } cout << ans << endl; }