Cod sursa(job #2182998)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 22 martie 2018 18:57:47
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 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))
    {
        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;
}