#include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e9 typedef struct{ int to; int cap; int cost; int rev; }edge; //min cost : s->t (flow:f) int min_cost_flow(vector > &G, int s, int t, int f){ const int N = G.size(); int cost = 0; vector prev_v(N,-1); vector prev_e(N,-1); while(f>0){ //min distance(cost based) search with SPFA vector dist(N, INF); vector cnt(dist.size(), 0); dist[s] = 0; prev_v[s] = s; queue Q; auto my_push = [&](int node){ Q.push(node); cnt[node]++; }; auto my_pop = [&]() -> int{ int ret = Q.front(); cnt[ret]--; Q.pop(); return ret; }; my_push(s); while(!Q.empty()){ int pos = my_pop(); for(int i=0; i dist[pos] + E.cost && E.cap > 0){ dist[E.to] = dist[pos] + E.cost; prev_v[ E.to ] = pos; prev_e[ E.to ] = i; if(cnt[ E.to ] == 0){ my_push( E.to ); } } } } //cannot achieved to "t" return -1 if(dist[t]>=INF) return -1; //add cost of s->t with flow=d int pos=t; int d=INF; while(pos!=s){ int i=prev_v[pos]; int j=prev_e[pos]; pos = i; d = min(d, G[i][j].cap); } pos = t; //cout << t ; while(pos!=s){ int i=prev_v[pos]; int j=prev_e[pos]; G[i][j].cap -= d; G[ G[i][j].to ][ G[i][j].rev ].cap += d; //cost += G[i][j].cost * d; pos = i; //cout << " <- " << pos; } //cout << endl; cost += d * dist[t]; f -= d; //f==0 then end } return cost; } void add_edge(vector > &G, int from, int to, int cap, int cost){ G[from].push_back((edge){to, cap, cost, (int)G[to].size()}); G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1}); } int main(){ int G,C,P; cin >> G >> C >> P; string S; cin >> S; int n = S.size(); vector> Graph(n + 3 + 2); int s = n+3+0; int t = n+3+1; int g = n+0; int c = n+1; int p = n+2; for(int i=0; i