Cod sursa(job #2179945)

Utilizator amaliarebAmalia Rebegea amaliareb Data 20 martie 2018 15:41:55
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("pixels.in");
ofstream g("pixels.out");
const int MaxN = 105;
int n, from[MaxN * MaxN], frpoz[MaxN * MaxN], S, D, added;
bool viz[MaxN * MaxN];
vector<pair<int, int> > gr[MaxN * MaxN];

inline int node(int i, int j) {
    return (i - 1) * n + j;
}

inline void muchie(int a, int b, int c) {
    gr[a].push_back({b, c});
    gr[b].push_back({a, c});
}

inline int getcap(int a, int b) {
    int A = gr[a].size();
    for (int i = 0; i < A; ++i)
        if (gr[a][i].first == b) return gr[a][i].second;
    return 0;
}

bool bfs()
{
    queue<int> q;
    memset(from, 0, sizeof(from));
    memset(viz, 0, sizeof(viz));
    viz[S] = 1;
    q.push(S);
    while (!q.empty() && !viz[D])
    {
        int node = q.front();
        q.pop();
        int sz = gr[node].size();
        for (int i = 0; i < sz; ++i)
        {
            int son = gr[node][i].first, cap = gr[node][i].second;
            if (!viz[son] && cap > 0)
            {
                viz[son] = 1;
                q.push(son);
                from[son] = node;
                frpoz[son] = i;
            }
        }
    }
    if (viz[D]) return 1;
    return 0;
}

int main()
{
    f >> n;
    S = n * n + 1;
    D = n * n + 2;
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int a;
            f >> a;
            muchie(S, node(i, j), a);
            sum += a;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int a;
            f >> a;
            muchie(node(i, j), D, a);
            sum += a;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int a;
            f >> a; f >> a;
            if (j < n) muchie(node(i, j), node(i, j + 1), a);
            f >> a;
            if (i < n) muchie(node(i, j), node(i + 1, j), a);
            f >> a;
        }
    }
    int maxfl = 0, added = 0;
    while (bfs())
    {
        added = 1e9;
        int node = D;
        while (node != S) {
            added = min(added, gr[from[node]][frpoz[node]].second);
            node = from[node];
        }
        node = D;
        while (node != S) {
            int sz = gr[node].size();
            for (int i = 0; i < sz; ++i) if (gr[node][i].first == from[node]) {
                gr[node][i].second += added;
                break;
            }
            gr[from[node]][frpoz[node]].second -= added;
            node = from[node];
        }
        maxfl += added;
    }
    g << sum - maxfl << ' ';
    return 0;
}