min cost max flow

gistfile1.cpp

#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAXN = 105;
const int MAXL = 105;
const int MAXNODE = 135;
const int MAXE = 105 * 105 * 2;
const int INF = 1 << 29;

int n;
char t[MAXL];
char s[MAXL];
struct Edge{
    int u, v, nxt;
    int cap, flow, cost;
}   e[MAXE];
int totalEdge, pnt[MAXNODE];
int ss, st;

void init(){
    if (scanf("%s%d", t, &n) == EOF) exit(0);
}

void addEdge(int u, int v, int cap, int cost){
    int i = totalEdge++;
    e[i].u = u;
    e[i].v = v;
    e[i].cap = cap;
    e[i].flow = 0;
    e[i].cost = cost;
    e[i].nxt = pnt[u];
    pnt[u] = i;
}

void addBi(int u, int v, int cap, int cost){
    addEdge(u, v, cap, cost);
    addEdge(v, u, 0, -cost);
}

void buildEdge(){
    ss = n + 26;
    st = ss + 1;
    totalEdge = 0;
    for (int i = 0;i <= st;i++) pnt[i] = -1;
    for (int i = 0;i < n;i++){
        int a;
        scanf("%s%d", s, &a);
        addBi(ss, i, a, i + 1);
        for (int j = 0;s[j];j++){
            addBi(i, s[j] - 'a' + n, 1, 0);
        }
    }
    for (int i = 0;t[i];i++){
        addBi(t[i] - 'a' + n, st, 1, 0);
    }
}

int pre[MAXNODE];
int dist[MAXNODE];
bool inq[MAXNODE];
void minCost(){
    int totalFlow = 0;
    int totalCost = 0;
    while (1){
        //find path
        for (int i = 0;i <= st;i++){
            dist[i] = INF;
            pre[i] = -1;
            inq[i] = false;
        }
        queue<int> q;
        while (!q.empty()) q.pop();
        dist[ss] = 0;
        q.push(ss);
        inq[ss] = true;
        while (!q.empty()){
            int cx = q.front();
            q.pop();
            inq[cx] = false;
            for (int i = pnt[cx];i >= 0;i = e[i].nxt){
                if (e[i].cap > e[i].flow){
                    int nx = e[i].v;
                    if (dist[nx] > dist[cx] + e[i].cost){
                        dist[nx] = dist[cx] + e[i].cost;
                        pre[nx] = i;
                        if (!inq[nx]){
                            q.push(nx);
                            inq[nx] = true;
                        }
                    }
                }
            }
        }
        //add flow
        if (pre[st] < 0) break;
        int curFlow = INF;
        for (int i = st;i != ss;i = e[pre[i]].u){
            curFlow = min(curFlow, e[pre[i]].cap - e[pre[i]].flow);
        }
        totalFlow += curFlow;
        totalCost += curFlow * dist[st];
        for (int i = st;i != ss;i = e[pre[i]].u){
            e[pre[i]].flow += curFlow;
            e[pre[i] ^ 1].flow -= curFlow;
        }
    }
    if (totalFlow < strlen(t)){
        printf("-1\n");
    }
    else{
        printf("%d\n", totalCost);
    }
}

void work(){
    buildEdge();
    minCost();
}

int main(){
#ifdef ILOAHZ
    freopen("c.in", "r", stdin);
#endif
    while (1){
        init();
        work();
    }
    return 0;
}

http://codeforces.com/problemset/problem/237/E