Cod sursa(job #2182985)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 22 martie 2018 18:51:24
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#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))
    {
        int Min=INF;
        for(int i=Sink;i!=Source;i=father[i].node)
            Min=min(Min,Edge[father[i].e].cap);
        for(int i=Sink;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;
        }
        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;
}