Cod sursa(job #3190126)

Utilizator GrigMihaiGrigore Mihai GrigMihai Data 7 ianuarie 2024 00:04:09
Problema Taramul Nicaieri Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.46 kb
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");

int n;
int graph[102][102], usedCap[102][102];
vector<int> augPath_rev;
int augumentation;

bool findAugPath()
{
    augPath_rev.clear();
    augumentation=INT_MAX;
    vector<int> dads(2*n+2, -1);

    queue<int> curLvl;
    queue<int> nextLvl;
    curLvl.push(0);
    bool found=false;
    while(!curLvl.empty())
    {
        while(!curLvl.empty())
        {
            int x=curLvl.front();
            curLvl.pop();
            
            if(x==0)
            {
                for(int i=1;i<=n;i++)
                    if(usedCap[x][i]<graph[x][i] && dads[i]==-1)
                    {
                        dads[i]=x;
                        augumentation=min(augumentation, graph[x][i]-usedCap[x][i]);
                        nextLvl.push(i);
                    }
            }
            else if(x<=n)
            {
                for(int i=n+1;i<=2*n;i++)
                    if(usedCap[x][i-n]<graph[x][i-n] && dads[i]==-1)
                    {
                        dads[i]=x;
                        augumentation=min(augumentation, graph[x][i-n]-usedCap[x][i-n]);
                        nextLvl.push(i);
                    }
            }
            else if(x<=2*n)
            {
                if(graph[x-n][n+1]>usedCap[x-n][n+1])
                {
                    dads[2*n+1]=x;
                    augumentation=min(augumentation, graph[x-n][n+1]-usedCap[x-n][n+1]);
                    curLvl=queue<int>();
                    nextLvl=queue<int>();
                    found=true;
                }
                else
                {
                    for(int i=1;i<=n;i++)
                        if(usedCap[i][x-n]>0 && dads[i]==-1)
                        {
                            dads[i]=x;
                            augumentation=min(augumentation, usedCap[i][x-n]);
                            nextLvl.push(i);
                        }
                }
            }
        }
        
        curLvl=nextLvl;
        nextLvl=queue<int>();
    }

    if(!found)
    {
        augumentation=0;
        return false;
    }

    int x=2*n+1;
    while(x!=-1) {
        augPath_rev.push_back(x);
        x = dads[x];
    }
    return true;
}

void augumentPath()
{
    int src, dst;
    src=augPath_rev[augPath_rev.size()-1];
    augPath_rev.pop_back();
    while(!augPath_rev.empty())
    {
        dst=augPath_rev[augPath_rev.size()-1];
        if(src==0)
            usedCap[src][dst]+=augumentation;
        else if(src<=n)
            usedCap[src][dst-n]+=augumentation;
        else if(dst==2*n+1)
            usedCap[src-n][dst-n]+=augumentation;
        else
            usedCap[src-n][dst]-=augumentation;
        src=dst;
        augPath_rev.pop_back();
    }
}

int main() {

    in>>n;
    int totalCap=0;
    for(int i=1;i<=n;i++)
    {
        in>>graph[0][i]>>graph[i][n+1];
        totalCap+=graph[0][i];
        for(int j=1;j<=n;j++)
            graph[i][j]=1;
        graph[i][i]=0;
    }

    while(findAugPath())
        augumentPath();

    /*int totalCap=0;
    for(int i=1;i<=n;i++) {
        //if (graph[0][i] == usedCap[0][i])
            totalCap+=usedCap[0][i];
        //else {
          //  out << 0;
            //return 0;
        //}
    }*/

    out<<totalCap<<'\n';
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(usedCap[i][j])
                out<<i<<' '<<j<<'\n';
    return 0;
}