1 /**************************************************************  2     Problem: 3396  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:0 ms  7     Memory:824 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cctype> 12 #include <cstring> 13 #include <algorithm> 14   15 using namespace std; 16 const int inf = (int) 1e9; 17 const int N = 65; 18 const int M = 1505; 19   20 struct edges{ 21     int next, to, f; 22     edges() {} 23     edges(int _next, int _to, int _f) : next(_next), to(_to), f(_f) {} 24 } e[M]; 25   26 int n; 27 int first[N], tot = 1, d[N], q[N]; 28 int S, T; 29   30 inline int read() { 31     int x = 0; 32     char ch = getchar(); 33     while (ch < ‘0‘ || ‘9‘ < ch) 34         ch = getchar(); 35     while (‘0‘ <= ch && ch <= ‘9‘) { 36         x = x * 10 + ch - ‘0‘; 37         ch = getchar(); 38     } 39     return x; 40 } 41   42 inline char getc() { 43     char ch = getchar(); 44     while (!isalpha(ch)) 45         ch = getchar(); 46     return ch; 47 } 48   49 inline void add_edge(int x, int y, int z){ 50     e[++tot] = edges(first[x], y, z); 51     first[x] = tot; 52 } 53     54 inline void Add_Edges(int x, int y, int z){ 55     add_edge(x, y, z); 56     add_edge(y, x, 0); 57 } 58   59 bool bfs(){ 60     memset(d, 0, sizeof(d)); 61     q[1] = S, d[S] = 1; 62     int l = 0, r = 1, x, y; 63     while (l < r){ 64         ++l; 65         for (x = first[q[l]]; x; x = e[x].next){ 66             y = e[x].to; 67             if (!d[y] && e[x].f) 68                 q[++r] = y, d[y] = d[q[l]] + 1; 69         } 70     } 71     return d[T]; 72 } 73     74 int dinic(int p, int limit){ 75     if (p == T || !limit) return limit; 76     int x, y, tmp, rest = limit; 77     for (x = first[p]; x; x = e[x].next){ 78         y = e[x].to; 79         if (d[y] == d[p] + 1 && e[x].f && rest){ 80             tmp = dinic(y, min(rest, e[x].f)); 81             rest -= tmp; 82             e[x].f -= tmp, e[x ^ 1].f += tmp; 83             if (!rest) return limit; 84         } 85     } 86     if (limit == rest) d[p] = 0; 87     return limit - rest; 88 } 89     90 int Dinic(){ 91     int res = 0, x; 92     while (bfs()) 93         res += dinic(S, inf); 94     return res; 95 } 96   97 int main() { 98     char ch; 99     int i, x, y, z;100     n = read();101     for (i = 1; i <= n; ++i) {102         ch = getc();103         if (‘A‘ <= ch && ch <= ‘Z‘)104             x = ch - ‘A‘ + 1;105         else x = ch - ‘a‘ + 27;106         ch = getc();107         if (‘A‘ <= ch && ch <= ‘Z‘)108             y = ch - ‘A‘ + 1;109         else y = ch - ‘a‘ + 27;110         z = read();111         Add_Edges(x, y, z);112     }113     S = 1, T = 26;114     printf("%d\n", Dinic());115     return 0;116 }