ISAP WA#7

#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 2147483647;
struct ISAP {
    struct Node { int from, to, cap; };
    vector<Node> edges;
    vector<int> G[55];
    int num[55], d[55], p[55], cur[55];
    int s = 1, t = 26, n, cn, cnt;
    inline void addEdge(int s, int t, int w) {
        edges.push_back({s, t, w});
        edges.push_back({t, s, 0});
        cnt += 2;
        G[s].push_back(cnt - 2);
        G[t].push_back(cnt - 1);
    }
    inline bool bfs() {
        queue<int> q;
        Node e;
        int u;
        d[t] = 1;
        q.push(t);
        while(!q.empty()) {
            u = q.front(), q.pop();
            for(int i = 0; i < G[u].size(); ++i) {
                e = edges[G[u][i] ^ 1];
                if(!d[e.from] && e.cap) {
                    d[e.from] = d[u] + 1;
                    q.push(e.from);
                }
            }
        }
        return d[s];
    }
    inline int Augument() {
        int x = t, a = INF;
        while(x != s) {
            a = min(a, edges[p[x]].cap);
            x = edges[p[x]].from;
        }
        x = t;
        while(x != s) {
            edges[p[x]].cap -= a;
            edges[p[x] ^ 1].cap += a;
            x = edges[p[x]].from;
        }
        return a;
    }
    int maxFlow() {
        int flow = 0, x = s;
        bfs();
        for(int i = 1; i <= 52; ++i)
            if(d[i]) ++num[d[i]];
        while(d[s] < cn) {
            if(x == t) {
                flow += Augument();
                x = s;
            }
            bool fl = 0;
            for(int i = cur[x]; i < G[x].size(); ++i) {
                Node& e = edges[G[x][i]];
                if(e.cap && d[x] == d[e.to] + 1) {
                    fl = 1;
                    p[e.to] = G[x][i];
                    cur[x] = i;
                    x = e.to;
                    break;
                }
            }
            if(!fl) {
                int minn = cn - 1;
                for(auto p : G[x]) {
                    Node& e = edges[p];
                    if(e.cap) minn = min(minn, d[e.to]);
                }
                if(--num[d[x]] == 0) break;
                ++num[d[x] = minn + 1];
                cur[x] = 0;
                if(x != s)
                    x = edges[p[x]].from;
            }
        }
        return flow;
    }
} mf;
int toN(char ch) {
    return (ch >= 'a' ? (ch - 'a' + 26) : (ch - 'A')) + 1;
}
char c1, c2;
bool used[54];
int u, v, w;
int main() {
    scanf("%d", &mf.n);
    for(int i = 1; i <= mf.n; ++i) {
        cin >> c1 >> c2 >> w;
        u = toN(c1);
        v = toN(c2);
        if(!used[u]) used[u] = 1, ++mf.cn;
        if(!used[v]) used[v] = 1, ++mf.cn;
        mf.addEdge(u, v, w);
    }
    printf("%d\n", mf.maxFlow());
}