Cod sursa(job #2179648)

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

#define BUF_SIZE 1 << 14
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline int nextnum(){
    int a = 0;
    char c = nextch();
    while(!isdigit(c))
        c = nextch();
    while(isdigit(c)){
        a = a * 10 + c - '0';
        c = nextch();
    }
    return a;
}

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(){
    fi = fopen("pixels.in","r");
    fo = fopen("pixels.out","w");

    n = nextnum();
    int s = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            int x = nextnum();
            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 = nextnum();
            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];
            c[0] = nextnum();
            c[1] = nextnum();
            c[2] = nextnum();
            c[3] = nextnum();
            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]){
            if(father[y.dest] && G[y.dest][1].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;
}