問題概要
文字列tとn個の文字列s1, s2, ...., snが与えられる。sを用いてtを作る。一回の操作で- s1, s2, ...., snの中から任意の文字列を一つを選ぶ。
- 1.で選んだ文字列から任意の一文字を選び、紙に書く。
- 選んだ文字列から選んだ文字を消去する。
この操作を複数回行い、紙に書かれた文字列がtと等しくなるようにする。ただし、それぞれのsi, i = 1,2, ..., nについて使用できる回数が決まっている。i番目の文字列を使用するとコストがiかかる。tを作るために必要な最小コストを求めよ。
方針
最小費用流を使う。乱択を使った解法でシステムテスト通過している人がいて、おもしろいなぁと思って同じようなことやってみたけど、以下のケースで落とせるじゃん。。ただ、この考え方は覚えておいて損は無さそうだ。
abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 1 abcdefghijklmnopqrstuvwxy 1 abcdefghijklmnopqrstuvwx 1 abcdefghijklmnopqrstuvw 1 abcdefghijklmnopqrstuv 1 abcdefghijklmnopqrstu 1 abcdefghijklmnopqrst 1 abcdefghijklmnopqrs 1 abcdefghijklmnopqr 1 abcdefghijklmnopq 1 abcdefghijklmnop 1 abcdefghijklmno 1 abcdefghijklmn 1 abcdefghijklm 1 abcdefghijkl 1 abcdefghijk 1 abcdefghij 1 abcdefghi 1 abcdefgh 1 abcdefg 1 abcdef 1 abcde 1 abcd 1 abc 1 ab 1 a 1
ソースコード
上が最小費用流を使った解法、下が乱択を使った解法。
using namespace std;
int V;
int main()
{
string tar;
int n;
cin >> tar >> n;
vector strs(n);
vector caps(n);
REP(i, n)
cin >> strs[i] >> caps[i];
V = 1 + n + 26 + 1;
REP (i, n) {
add_edge(0, 1+i, caps[i], 0);
REP (j, 26) {
int cnt = count(strs[i].begin(), strs[i].end(), (char)(j+'a'));
if (cnt)
add_edge(1+i, 1+n+j, cnt, i+1);
}
}
REP (i, 26) {
int cnt = count(tar.begin(), tar.end(), (char)(i+'a'));
if (cnt)
add_edge(1+n+i, 1+n+26, cnt, 0);
}
cout << min_cost_flow(0, 1+n+26, tar.length()) << endl;
return 0;
}
const int INF = 1<<30; string tar; int n; vectorstrs; vector caps; vector pri; int calc(vector &x, vector &y, char c) { REP (i, n) { if (y[i] == 0) continue; REP (j, x[i].length()) { if (x[i][j] == c) { x[i][j] = ' '; y[i]--; return i+1; } } } return INF; } int main() { cin >> tar >> n; strs.assign(n, ""); caps.assign(n, 0); pri.assign(tar.length(), 0); REP(i, n) cin >> strs[i] >> caps[i]; REP(i, tar.length()) pri[i] = i; int ret = INF; while (clock() < 1.8*CLOCKS_PER_SEC) { random_shuffle(pri.begin(), pri.end()); vector _strs = strs; vector _caps = caps; int total = 0; REP (k, tar.length()) { char c = tar[pri[k]]; int cost = calc(_strs, _caps, c); if (cost == INF) { total = INF; break; } else { total += cost; } } ret = min(ret, total); } if (ret == INF) cout << -1 << endl; else cout << ret << endl; return 0; }