25a.c (1857B)
1 #include <stdbool.h> 2 #include <stdio.h> 3 #include <string.h> 4 5 #define N 1500 6 #define ischar(c) (c >= 'a' && c <= 'z') 7 8 typedef struct { int nout, out[N]; char s[4], outc[N][4]; } node_t; 9 10 bool visited[N]; 11 char *buf, line[N][N]; 12 int n, nother, c[N][N], f[N][N]; 13 node_t m[N]; 14 15 int findm(char *s) { 16 for (int k = 0; k < n; k++) 17 if (m[k].s[0] == s[0] && m[k].s[1] == s[1] && m[k].s[2] == s[2]) 18 return k; 19 return n; 20 } 21 22 void resetfc(void) { 23 for (int i = 0; i < n; i++) 24 for (int j = 0; j < m[i].nout; j++) 25 c[i][m[i].out[j]] = 1; 26 for (int i = 0; i < n; i++) 27 memset(f[i], 0, N * sizeof(int)); 28 } 29 30 bool dfs(int v, int t) { 31 if (v == t) return true; 32 if (visited[v]) return false; 33 visited[v] = true; 34 for (int i = 0; i < m[v].nout; i++) { 35 int u = m[v].out[i]; 36 if (c[v][u] == 0) continue; 37 c[v][u]--; 38 c[u][v]++; 39 f[v][u]++; 40 if (dfs(u, t)) return true; 41 c[v][u]++; 42 c[u][v]--; 43 f[v][u]--; 44 } 45 return false; 46 } 47 48 bool residualpath(int s, int t) { 49 memset(visited, 0, N * sizeof(bool)); 50 return dfs(s, t); 51 } 52 53 /* Ford-Fulkerson */ 54 bool flowatmost(int s, int t, int k) { 55 int flow; 56 resetfc(); 57 for (flow = 0; flow <= k && residualpath(s, t); flow++) ; 58 return flow <= k; 59 } 60 61 int main() { 62 for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) { 63 for (int i = 0; ischar(*buf); m[n].s[i++] = *(buf++)) ; 64 for (int i = 0; *buf != '\n'; i++) { 65 while (!ischar(*buf)) buf++; 66 for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ; 67 } 68 } 69 70 for (int i = 0; i < n; i++) { 71 for (int j = 0; m[i].outc[j][0]; j++) { 72 int k = findm(m[i].outc[j]); 73 m[i].out[m[i].nout++] = k; 74 m[k].out[m[k].nout++] = i; 75 if (k == n) { 76 for (int k = 0; m[i].outc[j][k]; k++) 77 m[n].s[k] = m[i].outc[j][k]; 78 n++; 79 } 80 } 81 } 82 83 for (int t = 1; t < n; t++) 84 if (flowatmost(0, t, 3)) nother++; 85 86 printf("%d\n", nother * (n-nother)); 87 return 0; 88 }