Cod sursă (job #131879)

#include <stdio.h>
#include <string.h>
#define MAXN 1000
#define MAXM 5000
#define source 1
#define terminal n
#define INF 300000

using namespace std;

struct edge
{
    int dest;
    int next;
    int cap;
    int coresp;
}g[2*MAXM];

struct parent_tracking
{
    int p;
    int index;
}parent[MAXN+1];

int n, m, first[MAXN+1], maxflow, viz[MAXN+1], q[MAXN+1];
FILE *in, *out;

int mymin(int a, int b)
{
    if(a<b)
        return a;
    return b;
}

int BFS()
{
    int p=0, u=0, vf, k;
    memset(viz, 0, sizeof(viz));
    q[p]=source;
    viz[source]=1;
    while(p<=u)
    {
        vf=q[p];
        k=first[vf];
        while(k!=-1)
        {
            if(viz[g[k].dest]==0 && g[k].cap>0)
            {
                u++;
                q[u]=g[k].dest;
                viz[g[k].dest]=1;
                parent[g[k].dest].p=vf;
                parent[g[k].dest].index=k;
            }
            k=g[k].next;
        }
        p++;
    }
    return viz[terminal];
}

void BFS2()
{
    int p=0, u=0, vf, k;
    memset(viz, 0, sizeof(viz));
    q[p]=source;
    viz[source]=1;
    while(p<=u)
    {
        vf=q[p];
        k=first[vf];
        while(k!=-1)
        {
            if(viz[g[k].dest]==0 && g[k].cap>0)
            {
                u++;
                q[u]=g[k].dest;
                viz[g[k].dest]=1;
            }
            k=g[k].next;
        }
        p++;
    }
}

int main()
{
    in = fopen("mincut.in", "r");
    out = fopen("mincut.out", "w");

    memset(first, -1, sizeof(first));

    fscanf(in, "%d%d", &n, &m);

    for(int i=0; i<m; i++)
        g[i].coresp=-1;

    for(int i=0; i<2*m; i+=2)
    {
        int x, y, c;
        fscanf(in, "%d%d%d", &x, &y, &c);
        g[i].dest=y;
        g[i].next=first[x];
        first[x]=i;
        g[i].cap=c;
        g[i].coresp=i+1;
        g[i+1].dest=x;
        g[i+1].next=first[y];
        first[y]=i+1;
        g[i+1].cap=0;
        g[i+1].coresp=i;
    }

    maxflow=0;
    while(BFS())
    {
        int v=terminal, path_flow=INF;
        while(v!=source)
        {
            path_flow=mymin(path_flow, g[parent[v].index].cap);
            v=parent[v].p;
        }
        v=terminal;
        while(v!=source)
        {
            g[parent[v].index].cap-=path_flow;
            g[g[parent[v].index].coresp].cap+=path_flow;
            v=parent[v].p;
        }
        maxflow+=path_flow;
    }
    fprintf(out, "%d\n", maxflow);

    BFS2();
    for(int i=0; i<n; i++)
    {
        if(viz[i]==1)
        {
            int k=first[i];
            while(k!=-1)
            {
                if(viz[g[k].dest]==0)
                    fprintf(out, "%d %d\n", i, g[k].dest);
                k=g[k].next;
            }
        }
    }

    fclose(in);
    fclose(out);
    return 0;
}