maxflow modify

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

const int inf = 2000000007;

struct edge
{
    int to, from, cap, f;
};


vector<edge> E;
vector<vector<int> > g;
int S, I;
int used[10010], d[10100], pt[10010], t[10100];

void add_edge(int from, int to, int cap)
{
    edge e;
    e.to = to;
    e.from = from;
    e.cap = cap;
    e.f = 0;
    g[from].push_back(E.size());
    E.push_back(e);
    return;
}

void bfs()
{
    queue<int> q;
    d[I] = 0;
    q.push(I);
    used[I] = 1;
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (int i = 0; i < g[v].size(); i++)
        {
            int r = g[v][i];
            int to = E[r].to;
            if (!used[to] && E[r].cap > E[r].f)
            {
                q.push(to);
                d[to] = d[v] + 1;
                used[to] = 1;
            }
        }
    }
    return;
}

int dfs(int v, int flow = inf)
{
    if (flow == 0)
        return 0;

    if (v == S)
        return flow;

    int save = 0;
    for (; pt[v] < g[v].size(); pt[v]++)
    {
        int i = pt[v];
        int r = g[v][i];
        int to = E[r].to;
        if (d[to] != d[v] + 1)
            continue;
        int del = E[r].cap - E[r].f;
        int k = dfs(to, min(flow, del));
        if (k >= 0)
        {
            if (k > flow)
                k = flow;

            flow -= k;
            save += k;
            E[r].f += k;
            E[r ^ 1].f -= k;
            if (flow == 0)
                return save;
        }
    }
    return save;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    int x, y;
    for (int i = 0; i < n; i++)
        cin >> x >> y;
    g.resize(n);
    int m;
    cin >> m;
    int v, u, cap;
    I = 0;
    S = n - 1;
    for (int i = 0; i < m; i++)
    {
        cin >> v >> u >> cap;
        v--;
        u--;
        add_edge(v, u, cap);
        add_edge(u, v, 0);
        add_edge(u, v, cap);
        add_edge(v, u, 0);
    }

    int f = 0;
    int ans = 0;
    while (1)
    {
        for (int i = 0; i < n; i++)
        {
            d[i] = 0;
            used[i] = 0;
            pt[i] = 0;
        }

        bfs();

        if (d[S] == 0)
            break;

        f = dfs(I);
        if (f > 0)
            ans += f;
    }

    cout << ans << endl;

    for (int i = 0; i < E.size(); i += 4)
    {
        if (E[i].f > E[i + 2].f)
            printf("%d %d %d\n", E[i].from + 1, E[i].to + 1, E[i].f - E[i + 2].f);
        //cout << E[i].from + 1 << " " << E[i].to + 1 << " " << E[i].f - E[i+2].f << endl;
        else
            printf("%d %d %d\n", E[i].to + 1, E[i].from + 1, E[i + 2].f - E[i].f);
            //cout << E[i].to + 1 << " " << E[i].from + 1 << " " << E[i+2].f - E[i].f << endl;
    }

    system("PAUSE");

    return 0;
}