Pagini recente » Cod sursa (job #2795395) | Borderou de evaluare (job #804976) | Cod sursa (job #995179) | Cod sursa (job #7412) | Cod sursa (job #2182998)
#include <bits/stdc++.h>
#define MaxN 105
#define INF 2140000000
#define MOD 666013
using namespace std;
FILE *IN=fopen("pixels.in","r"),*OUT=fopen("pixels.out","w");
int N,C[4],cnt,Ans=0;
vector<int>Graph[MaxN*MaxN];
struct spec
{
int son,cap;
}Edge[8*MaxN*MaxN];
struct spec2
{
int node,e;
}father[MaxN*MaxN];
queue<int>Q;
bool BFS(int node,int dest)
{
for(int i=0;i<=N*N+1;i++)
father[i]={-1,0};
Q.push(node);
father[node].node=0;
while(!Q.empty())
{
node=Q.front();
Q.pop();
for(int i=0;i<Graph[node].size();i++)
{
int x=Graph[node][i];
if(father[Edge[x].son].node==-1&&Edge[x].cap)
{
father[Edge[x].son].node=node;
father[Edge[x].son].e=x;
Q.push(Edge[x].son);
}
}
}
return father[dest].node!=-1;
}
inline int Flow(int Source,int Sink)
{
int F=0;
while(BFS(Source,Sink))
{
for(int k=0;k<Graph[Sink].size();k++)
if(Edge[Graph[Edge[Graph[Sink][k]].son][1]].cap)
{
int node=Edge[Graph[Sink][k]].son;
int Min=Edge[Graph[node][1]].cap;
for(int i=node;i!=Source;i=father[i].node)
Min=min(Min,Edge[father[i].e].cap);
for(int i=node;i!=Source;i=father[i].node)
{
int x;
Edge[father[i].e].cap-=Min;
if(father[i].e%2==0)
x=father[i].e+1;
else x=father[i].e-1;
Edge[x].cap+=Min;
}
Edge[Graph[Sink][k]].cap+=Min;
Edge[Graph[node][1]].cap-=Min;
F+=Min;
}
}
return F;
}
int main()
{
fscanf(IN,"%d",&N);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
fscanf(IN,"%d",&C[0]);
Edge[cnt]={(i-1)*N+j,C[0]};
Graph[0].push_back(cnt++);
Edge[cnt]={0,C[0]};
Graph[(i-1)*N+j].push_back(cnt++);
Ans+=C[0];
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
fscanf(IN,"%d",&C[0]);
Edge[cnt]={(i-1)*N+j,C[0]};
Graph[N*N+1].push_back(cnt++);
Edge[cnt]={N*N+1,C[0]};
Graph[(i-1)*N+j].push_back(cnt++);
Ans+=C[0];
}
for(int i=1;i<=N*N;i++)
{
fscanf(IN,"%d%d%d%d",&C[0],&C[1],&C[2],&C[3]);
Edge[cnt]={i+1,C[1]};
Graph[i].push_back(cnt++);
Edge[cnt]={i,C[1]};
Graph[i+1].push_back(cnt++);
Edge[cnt]={i+N,C[2]};
Graph[i].push_back(cnt++);
Edge[cnt]={i,C[2]};
Graph[i+N].push_back(cnt++);
}
fprintf(OUT,"%d",Ans-Flow(0,N*N+1));
return 0;
}