const int MAXV = 2005;const int INF = 1<<30;struct Edge{ int to, cap, rev; };std::vector<Edge> G[MAXV];bool used[MAXV];void addedge(int from, int to, int cap) {    G[from].push_back(Edge{to, cap, G[to].size()});    G[to].push_back(Edge{from, 0, G[from].size()-1});}int dfs(int v, int t, int f) {    if (v == t) return f;    used[v] = true;    for (int i = 0; i < G[v].size(); ++i) {        Edge &e = G[v][i];        if (!used[e.to] && e.cap > 0) {            int d = dfs(e.to, t, std::min(f, e.cap));            if (d > 0) {                e.cap -= d;                G[e.to][e.rev].cap += d;                return d;            }        }    }    return 0;}int maxflow(int s, int t) {    int flow = 0;    for (; ;) {        memset(used, 0, sizeof used);        int f = dfs(s, t, INF);        if (!f) return flow;        flow += f;    }    return flow;}

#include <queue>#include <cstring>const int N = 2005;const int M = 2005;const int INF = 0x7fffffff;struct Edge {    int from, to, next, cost;} edge[M];int head[N];int cnt_edge;void add_edge(int u, int v, int c){    edge[cnt_edge].to = v;    edge[cnt_edge].from = u;    edge[cnt_edge].cost = c;    edge[cnt_edge].next = head[u];    head[u] = cnt_edge++;}int pre[N], flow[N];std::queue<int> q;int bfs(int src, int des){    memset(pre, -1, sizeof pre);    while (!q.empty()) q.pop();    q.push(src);    flow[src] = INF;    while (!q.empty())    {        int u = q.front();        q.pop();        if (u == des) break;        for (int i = head[u]; i != -1; i = edge[i].next)        {            int v = edge[i].to;            int cost = edge[i].cost;            if (pre[v] == -1 && cost > 0)            {                flow[v] = std::min(flow[u], cost);                pre[v] = i; // 记录的是边                q.push(v);            }        }    }    if (pre[des] == -1) return -1;    return flow[des];}int maxFlow(int src, int des){    int ans = 0;    int in;    while ((in = bfs(src, des)) != -1)    {        int k = des;        while (k != src)        {            int last = pre[k];            edge[last].cost -= in;            edge[last ^ 1].cost += in;            k = edge[last].from;        }        ans += in;    }    return ans;}int main(){    int n, m;    while (~scanf("%d%d", &m, &n))    {        int a, b, c;        memset(head, -1, sizeof head);        while (m--)        {            scanf("%d%d%d", &a, &b, &c);            add_edge(a, b, c);            add_edge(b, a, 0);        }        printf("%d\n", maxFlow(1, n));    }}

#include <cstdio>#include <vector>#include <cstring>#include <queue>const int MAXV = 2005;const int INF = 1<<30;struct Edge{ int to, cap, rev; };std::vector<Edge> G[MAXV];int level[MAXV];int iter[MAXV]; //当前弧，之前的已经没有用了void addedge(int from, int to, int cap) {    G[from].push_back(Edge{to, cap, G[to].size()});    G[to].push_back(Edge{from, 0, G[from].size()-1});}void bfs(int s) {    memset(level, -1, sizeof level);    std::queue<int> que;    level[s] = 0;    que.push(s);    while (!que.empty()) {        int v = que.front(); que.pop();        for (int i = 0; i < G[v].size(); ++i) {            Edge &e = G[v][i];            if (e.cap > 0 && level[e.to] < 0) {                level[e.to] = level[v] + 1;                que.push(e.to);            }        }    }}int dfs(int v, int t, int f) {    if (v == t) return f;    for (int &i = iter[v]; i < G[v].size(); ++i) { // 注意i是引用 实现当前弧优化        Edge &e = G[v][i];        if (e.cap > 0 && level[v] < level[e.to]) {            int d = dfs(e.to, t, std::min(f, e.cap));            if (d > 0) {                e.cap -= d;                G[e.to][e.rev].cap += d;                return d;            }        }    }    return 0;}int maxflow(int s, int t) {    int flow = 0;    for (; ;) {        bfs(s);        if (level[t] < 0) return flow;        memset(iter, 0, sizeof iter);        int f;        while ((f = dfs(s, t, INF)) > 0) {            flow += f;        }    }    return flow;}

const int N = 1000;const int M = 1000000;const int INF = 1 << 30;struct Edge {    int from, to, next, w;//from一般用不到} edge[M];int head[N], cntE;int src, sink;int pre[N], cur[N], dis[N], gap[N];int que[N], open, tail;void addedge(int u, int v, int w) {    edge[cntE].from = u;    edge[cntE].to = v;    edge[cntE].w = w;    edge[cntE].next = head[u];    head[u] = cntE++;    edge[cntE].from = v;    edge[cntE].to = u;    edge[cntE].w = 0;    edge[cntE].next = head[v];    head[v] = cntE++;}void BFS() {    int i, u, v;    memset(gap, 0, sizeof(gap));    memset(dis, -1, sizeof(dis));    open = tail = 0;    que[open] = sink;    dis[sink] = 0;    while (open <= tail) {        u = que[open++];        for (i = head[u]; ~i; i = edge[i].next) {            v = edge[i].to;            if (edge[i].w != 0 || dis[v] != -1) continue;            que[++tail] = v;            ++gap[dis[v] = dis[u] + 1];        }    }}int sap(int n) { //编号从1开始 1~n    int i, v, u, flow = 0, aug = INF;    int flag;    BFS();    gap[0] = 1;    for (i = 1; i <= n; i++) cur[i] = head[i];    u = pre[src] = src;    while (dis[src] < n) {        flag = 0;        for (int j = cur[u]; ~j; j = edge[j].next) {            v = edge[j].to;            if (edge[j].w > 0 && dis[u] == dis[v] + 1) {                flag = 1;                if (edge[j].w < aug) aug = edge[j].w;                pre[v] = u; u = v;                if (u == sink) {                    flow += aug;                    while (u != src) {                        u = pre[u];                        edge[cur[u]].w -= aug;                        edge[cur[u] ^ 1].w += aug;                    }                    aug = INF;                }                break;            }            cur[u] = edge[j].next;        }        if (flag) continue;        int mindis = n;        for (int j = head[u]; ~j; j = edge[j].next) {            v = edge[j].to;            if (edge[j].w > 0 && mindis > dis[v]) {                mindis = dis[v];                cur[u] = j;            }        }        if (--gap[dis[u]] == 0) break;        ++gap[dis[u] = mindis + 1];        u = pre[u];    }    return flow;}int main() {    memset(head, -1, sizeof head);    cntE = 0;}