Cod sursa(job #1389479)

Utilizator geniucosOncescu Costin geniucos Data 16 martie 2015 12:12:18
Problema Pixels Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

int ;

class graph
{
public:
    int N, S, D, t[1009], f[1009][1009], c[1009][1009];
    vector < int > v[1009];

    void add_edge (int x, int y, int cap)
    {
        c[x][y] = cap;
        v[x].push_back (y);
        v[y].push_back (x);
    }

    bool bfs ()
    {
        queue < int > cc;
        for (int i=1; i<=N; i++)
            t[i] = -1;

        cc.push (S);
        t[S] = 0;
        while (!cc.empty())
        {
            int nod = cc.front ();
            cc.pop();
            for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
                if (t[*it] == -1 && f[nod][*it] < c[nod][*it])
                {
                    t[*it] = nod;
                    cc.push (*it);
                    if (*it == D)
                        return 1;
                }
        }
        return 0;
    }

    int flux ()
    {
        int F = 0;
        while (bfs ())
        {
            for (vector < int > :: iterator it = v[D].begin(); it != v[D].end(); it ++)
                if (f[*it][D] < c[*it][D])
                {
                    int mini = 1000000;

                    t[D] = *it;
                    for (int i=D; i != S; i = t[i])
                        if (c[t[i]][i] - f[t[i]][i] < mini)
                            mini = c[t[i]][i] - f[t[i]][i];

                    F += mini;

                    for (int i=D; i != S; i = t[i])
                    {
                        f[t[i]][i] += mini;
                        f[i][t[i]] -= mini;
                    }
                }
        }
        return F;
    }
};

int main()
{
freopen ("pixels.in", "r", stdin);
freopen ("pixels.out", "w", stdout);



return 0;
}