Codeforces 237 E Build String【費用フロー】
12343 ワード
タイトルリンク:Codeforces 237 E Build String
E. Build String time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You desperately need to build some string t. For that you’ve got n more strings s1, s2, …, sn. To build string t, you are allowed to perform exactly |t| (|t| is the length of string t) operations on these strings. Each operation looks like that:
choose any non-empty string from strings s1, s2, …, sn; choose an arbitrary character from the chosen string and write it on a piece of paper; remove the chosen character from the chosen string. Note that after you perform the described operation, the total number of characters in strings s1, s2, …, sn decreases by 1. We are assumed to build string t, if the characters, written on the piece of paper, in the order of performed operations form string t.
There are other limitations, though. For each string si you know number ai — the maximum number of characters you are allowed to delete from string si. You also know that each operation that results in deleting a character from string si, costs i rubles. That is, an operation on string s1 is the cheapest (it costs 1 ruble), and the operation on string sn is the most expensive one (it costs n rubles).
Your task is to count the minimum amount of money (in rubles) you will need to build string t by the given rules. Consider the cost of building string t to be the sum of prices of the operations you use.
Input The first line of the input contains string t — the string that you need to build.
The second line contains a single integer n (1 ≤ n ≤ 100) — the number of strings to which you are allowed to apply the described operation. Each of the next n lines contains a string and an integer. The i-th line contains space-separated string si and integer ai (0 ≤ ai ≤ 100). Number ai represents the maximum number of characters that can be deleted from string si.
All strings in the input only consist of lowercase English letters. All strings are non-empty. The lengths of all strings do not exceed 100 characters.
Output Print a single number — the minimum money (in rubles) you need in order to build string t. If there is no solution, print -1.
Examples input bbaze 3 bzb 2 aeb 3 ba 10 output 8 input abacaba 4 aba 2 bcc 1 caa 2 bbb 5 output 18 input xyz 4 axx 8 za 1 efg 4 t 1 output -1 Note Notes to the samples:
In the first sample from the first string you should take characters “b” and “z” with price 1 ruble, from the second string characters “a”, “e” и “b” with price 2 rubles. The price of the string t in this case is 2·1 + 3·2 = 8.
In the second sample from the first string you should take two characters “a” with price 1 ruble, from the second string character “c” with price 2 rubles, from the third string two characters “a” with price 3 rubles, from the fourth string two characters “b” with price 4 rubles. The price of the string t in this case is 2·1 + 1·2 + 2·3 + 2·4 = 18.
In the third sample the solution doesn’t exist because there is no character “y” in given strings.
題意:主列sを1つ与えて、今あなたにn個のモード列をあげて、i番目の列から1つの文字を出す代価はiで、最大num[i]の文字を出します.最小の代価を出力できればsを構築できるかどうかを聞いてください.
構想:裸の費用が流れた.ソースから26文字のエッジを作成し、容量はs列の文字の個数で、費用は0です.各文字はn個のモード列にエッジを構築し、記列iにcnt個の文字があれば、容量cnt、費用iのエッジを構築する.最後に、各モードはnum[i]、費用0の直列結合エッジである.
最後の結果,満流はs列を構築できることを示し,逆にできないことを示した.
ACコード:
E. Build String time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You desperately need to build some string t. For that you’ve got n more strings s1, s2, …, sn. To build string t, you are allowed to perform exactly |t| (|t| is the length of string t) operations on these strings. Each operation looks like that:
choose any non-empty string from strings s1, s2, …, sn; choose an arbitrary character from the chosen string and write it on a piece of paper; remove the chosen character from the chosen string. Note that after you perform the described operation, the total number of characters in strings s1, s2, …, sn decreases by 1. We are assumed to build string t, if the characters, written on the piece of paper, in the order of performed operations form string t.
There are other limitations, though. For each string si you know number ai — the maximum number of characters you are allowed to delete from string si. You also know that each operation that results in deleting a character from string si, costs i rubles. That is, an operation on string s1 is the cheapest (it costs 1 ruble), and the operation on string sn is the most expensive one (it costs n rubles).
Your task is to count the minimum amount of money (in rubles) you will need to build string t by the given rules. Consider the cost of building string t to be the sum of prices of the operations you use.
Input The first line of the input contains string t — the string that you need to build.
The second line contains a single integer n (1 ≤ n ≤ 100) — the number of strings to which you are allowed to apply the described operation. Each of the next n lines contains a string and an integer. The i-th line contains space-separated string si and integer ai (0 ≤ ai ≤ 100). Number ai represents the maximum number of characters that can be deleted from string si.
All strings in the input only consist of lowercase English letters. All strings are non-empty. The lengths of all strings do not exceed 100 characters.
Output Print a single number — the minimum money (in rubles) you need in order to build string t. If there is no solution, print -1.
Examples input bbaze 3 bzb 2 aeb 3 ba 10 output 8 input abacaba 4 aba 2 bcc 1 caa 2 bbb 5 output 18 input xyz 4 axx 8 za 1 efg 4 t 1 output -1 Note Notes to the samples:
In the first sample from the first string you should take characters “b” and “z” with price 1 ruble, from the second string characters “a”, “e” и “b” with price 2 rubles. The price of the string t in this case is 2·1 + 3·2 = 8.
In the second sample from the first string you should take two characters “a” with price 1 ruble, from the second string character “c” with price 2 rubles, from the third string two characters “a” with price 3 rubles, from the fourth string two characters “b” with price 4 rubles. The price of the string t in this case is 2·1 + 1·2 + 2·3 + 2·4 = 18.
In the third sample the solution doesn’t exist because there is no character “y” in given strings.
題意:主列sを1つ与えて、今あなたにn個のモード列をあげて、i番目の列から1つの文字を出す代価はiで、最大num[i]の文字を出します.最小の代価を出力できればsを構築できるかどうかを聞いてください.
構想:裸の費用が流れた.ソースから26文字のエッジを作成し、容量はs列の文字の個数で、費用は0です.各文字はn個のモード列にエッジを構築し、記列iにcnt個の文字があれば、容量cnt、費用iのエッジを構築する.最後に、各モードはnum[i]、費用0の直列結合エッジである.
最後の結果,満流はs列を構築できることを示し,逆にできないことを示した.
ACコード:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <queue>
#define CLR(a, b) memset(a, (b), sizeof(a))
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 1e6 + 1;
const int MOD = 1073741824;
const int INF = 0x3f3f3f3f;
void add(LL &x, LL y) { x += y; x %= MOD; }
int num[40], use[110];
char str[110];
int cnt[110][40];
struct Edge {
int from, to, cap, flow, cost, next;
};
Edge edge[10000];
int head[200], edgenum;
void init() { CLR(head, -1); edgenum = 0; }
void addEdge(int u, int v, int w, int c) {
Edge E = {u, v, w, 0, c, head[u]};
edge[edgenum] = E;
head[u] = edgenum++;
Edge E1 = {v, u, 0, 0, -c, head[v]};
edge[edgenum] = E1;
head[v] = edgenum++;
}
bool vis[200];
int dist[200], pre[200];
bool SPFA(int s, int t) {
queue<int> Q; CLR(dist, INF); CLR(vis, false); CLR(pre, -1);
vis[s] = true; dist[s] = 0; Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = edge[i].next) {
Edge E = edge[i];
if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow) {
dist[E.to] = dist[u] + E.cost;
pre[E.to] = i;
if(!vis[E.to]) {
vis[E.to] = true;
Q.push(E.to);
}
}
}
}
return pre[t] != -1;
}
void MCMF(int s, int t, int &flow, int &cost) {
flow = cost = 0;
while(SPFA(s, t)) {
int Min = INF;
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) {
Edge E = edge[i];
Min = min(Min, E.cap - E.flow);
}
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) {
edge[i].flow += Min;
edge[i^1].flow -= Min;
//cout << edge[i].cost << endl;
cost += edge[i].cost * Min;
}
flow += Min;
}
}
int main()
{
while(scanf("%s", str) != EOF) {
int len = strlen(str); CLR(num, 0);
int sum = len;
for(int i = 0; i < len; i++) {
int v = str[i] - 'a' + 1;
num[v]++;
}
int n; scanf("%d", &n); CLR(cnt, 0);
for(int i = 1; i <= n; i++) {
scanf("%s%d", str, &use[i]);
len = strlen(str);
for(int j = 0; j < len; j++) {
int v = str[j] - 'a' + 1;
cnt[i][v]++;
}
}
init();
int s = 0, t = 26+n+1;
for(int i = 1; i <= 26; i++) {
if(num[i] == 0) continue;
addEdge(s, i, num[i], 0);
for(int j = 1; j <= n; j++) {
if(cnt[j][i] == 0) continue;
addEdge(i, 26+j, cnt[j][i], j);
}
}
for(int i = 1; i <= n; i++) {
addEdge(26+i, t, use[i], 0);
}
int flow, cost;
MCMF(s, t, flow, cost);
if(flow != sum) {
printf("-1
");
}
else {
printf("%d
", cost);
}
}
return 0;
}