Cod sursa(job #2179639)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 20 martie 2018 13:01:06
Problema Pixels Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <bits/stdc++.h>
#define MAXN 10010

int n, S = MAXN - 1, D = MAXN, flux;
struct Edge{int dest, cap;};
std::vector <Edge> G[1 + MAXN];
int father[1 + MAXN];
int q[1 + MAXN], p, u;

inline bool bfs(){
    memset(father, 0, sizeof(father));
    p = 0, u = 1;
    q[0] = S;
    while(p != u){
        int node = q[p++];
        for(int i = 0; i < G[node].size(); i++)
            if(!father[G[node][i].dest] && G[node][i].cap) father[G[node][i].dest] = node, q[u++] = G[node][i].dest;
        if(father[D]) return 1;
    }
    return 0;
}
inline void addEdge(int a, int b, int cap){
    G[a].push_back({b, cap});
    G[b].push_back({a, cap});
}

int main(){
    FILE*fi,*fo;
    fi = fopen("pixels.in","r");
    fo = fopen("pixels.out","w");

    fscanf(fi,"%d", &n);
    int s = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            int x;
            fscanf(fi,"%d", &x);
            addEdge(S, (i - 1) * n + j, x);
            s += x;
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            int x;
            fscanf(fi,"%d", &x);
            addEdge((i - 1) * n + j, D, x);
            s += x;
        }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            int c[4];
            fscanf(fi,"%d%d%d%d", &c[0], &c[1], &c[2], &c[3]);
            if(j + 1 <= n) addEdge((i - 1) * n + j, (i - 1) * n + j + 1, c[1]);
            if(i + 1 <= n) addEdge((i - 1) * n + j, (i + 1 - 1) * n + j, c[2]);
        }

    while(bfs())
        for(auto y: G[D]){
            int i = 0;
            while(G[y.dest][i].dest != D) i++;
            if(father[y.dest] && G[y.dest][i].cap){
                father[D] = y.dest;
                int flow = 1000000000;
                for(int i = D; i != S; i = father[i]){
                    int j = 0;
                    while(G[father[i]][j].dest != i) j++;
                    flow = std::min(flow, G[father[i]][j].cap);
                }
                for(int i = D; i != S; i = father[i]){
                    int j = 0;
                    while(G[father[i]][j].dest != i) j++;
                    G[father[i]][j].cap -= flow;
                    j = 0;
                    while(G[i][j].dest != father[i]) j++;
                    G[i][j].cap += flow;
                }
                flux += flow;
            }
        }
    fprintf(fo,"%d", s - flux);
    return 0;
}