Pagini recente » Cod sursa (job #553975) | Cod sursa (job #605258) | Cod sursa (job #2156030) | Cod sursa (job #1869583) | Cod sursa (job #2179648)
#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;
}