1 const int maxn = 405; 2 const int maxm = maxn * maxn; 3 const int inf = 1000000000; 4  5 class Dinic { 6 public : 7     struct Node { 8         int u, v, f, next; 9     }e[maxm];10 11     int head[maxn], p, lev[maxn], cur[maxn];12     int que[maxm];13 14     void init() {15         p = 0; 16         memset(head, -1, sizeof(head));17     }18 19     void add(int u, int v, int f) {20         e[p].u = u; e[p].v = v; e[p].f = f; e[p].next = head[u]; head[u] = p++;21         e[p].u = v; e[p].v = u; e[p].f = 0; e[p].next = head[v]; head[v] = p++;22     }23 24     bool bfs(int s, int t) {25         int u, v, qin = 0, qout = 0;26         memset(lev, 0, sizeof(lev)); lev[s] = 1; que[qin++] = s;27         while(qout != qin) {28             u = que[qout++];29             for(int i = head[u]; i != -1; i = e[i].next) {30                 if(e[i].f > 0 && !lev[v = e[i].v]) {31                     lev[v] = lev[u] + 1, que[qin++] = v;32                     if(v == t) return 1;33                 }34             }35         }36         return 0;37     }38 39     int dfs(int s, int t) {40         int i, f, qin, u, k;41         int flow = 0;42         while(bfs(s, t)) {43             memcpy(cur, head, sizeof(head));44             u = s, qin = 0;45             while(1) {46                 if(u == t) {47                     for(k = 0, f = inf; k < qin; k++)48                         if(e[que[k]].f < f) f = e[que[i=k]].f;49                     for(k = 0; k < qin; k++)50                         e[que[k]].f -= f, e[que[k]^1].f += f;51                     flow += f, u = e[que[qin = i]].u;52                 }53                 for(i = cur[u]; cur[u] != -1; i = cur[u] = e[cur[u]].next)54                     if(e[i].f > 0 && lev[u] + 1 == lev[e[i].v]) break;55                 if(cur[u] != -1)56                     que[qin++] = cur[u], u = e[cur[u]].v;57                 else {58                     if(qin == 0) break;59                     lev[u] = -1, u = e[que[--qin]].u;60                 }61             }62         }63         return flow;64     }65 };66 67 Dinic g;