Cod sursa(job #1418604)

Utilizator geniucosOncescu Costin geniucos Data 13 aprilie 2015 15:14:38
Problema Pixels Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

int N, ans, cod[109][109];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

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

    int M, F[120009], C[120009], y[120009];////edges

    void add_edge (int left, int right, int cap)
    {
        y[++M] = right, C[M] = cap, F[M] = 0, v[left].push_back (M);
        y[++M] = left, C[M] = 0, F[M] = 0, v[right].push_back (M);
    }

    int rev (int M)
    {
        if (M & 1)
            return M + 1;
        return M - 1;
    }

    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[y[*it]] == -1 && F[*it] < C[*it])
                {
                    t[y[*it]] = *it;
                    cc.push (y[*it]);
                    if (y[*it] == D)
                        return 1;
                }
        }
        return 0;
    }

    int flux ()
    {
        int sol = 0;
        while (bfs ())
        {
            for (vector < int > :: iterator it = v[D].begin(); it != v[D].end(); it ++)
                if (F[rev(*it)] < C[rev(*it)] && t[y[*it]] != -1)
                {
                    int mini = 1000000;

                    t[D] = rev(*it);
                    for (int i=D; i != S; i = y[rev(t[i])])
                    {
                        if (C[t[i]] - F[t[i]] < mini)
                            mini = C[t[i]] - F[t[i]];
                    }

                    sol += mini;

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

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

scanf ("%d", &N);
graf.S = 1;
graf.D = graf.N = 2;

for (int i=1; i<=N; i++)
    for (int j=1; j<=N; j++)
    {
        cod[i][j] = ++graf.N;
        int x;
        scanf ("%d", &x);
        ans += x;
        graf.add_edge (graf.S, cod[i][j], x);
    }

for (int i=1; i<=N; i++)
    for (int j=1; j<=N; j++)
    {
        int x;
        scanf ("%d", &x);
        ans += x;
        graf.add_edge (cod[i][j], graf.D, x);
    }

for (int i=1; i<=N; i++)
    for (int j=1; j<=N; j++)
        for (int k=0; k<4; k++)
        {
            int x;
            scanf ("%d", &x);
            if (i + dx[k] >= 1 && j + dy[k] >= 1 && i + dx[k] <= N && j + dy[k] <= N)
                graf.add_edge (cod[i][j], cod[i+dx[k]][j+dy[k]], x);
        }

printf ("%d\n", ans - graf.flux ());

return 0;
}