Cod sursa(job #2960872)

Utilizator adeladanescuAdela Danescu adeladanescu Data 5 ianuarie 2023 03:23:34
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<vector<int>> la;
vector<int> parinte;
int M, dest, x,y, capacitate[201][201], maxim=INT_MAX;
long max_flow = 0;

void read()
{
    dest= 2 * M + 1;
    la.resize(201);
    parinte.resize(2 * M + 1);

    for(int i=1; i <= M; i++)
    {
        fin >> x >> y;
        la[0].push_back(i);
        la[i].push_back(0);
        la[dest].push_back(i + M);
        la[i + M].push_back(dest);
        capacitate[0][i]=x;
        capacitate[i + M][dest]=y;
    }
    for(int i=1; i <= M; i++)
        for(int j= 1 + M; j <= 2 * M; j++)
        {
            if(i!= j - M)
            {
                la[i].push_back(j);
                la[j].push_back(i);
                capacitate[i][j]=1;
            }
        }
}
int bfs()
{
    vector<bool> viz(2 * M + 1);
    queue<int> coada;
    coada.push(0);
    viz[0] = true;
    parinte[0] = -1;
    while(!coada.empty())
    {
        int u = coada.front();
        coada.pop();
        for(auto v: la[u])
        {
            if(viz[v]==false && capacitate[u][v]!=0)
            {
                parinte[v] = u;
                if(v == dest)
                    return 1;
                viz[v] = true;
                coada.push(v);
            }
        }
    }
    return 0;
}

void maxflow()
{

    int new_flow=bfs();
    while(new_flow)
    {
        int temp, next=dest, path_flow = maxim;
        while(next != 0)
        {
            temp = parinte[next];
            path_flow=min(capacitate[temp][next],path_flow);
            next = parinte[next];
        }
        next=dest;
        while(next != 0)
        {
            temp = parinte[next];
            capacitate[temp][next] -= path_flow;
            capacitate[next][temp] += path_flow;
            next = parinte[next];
        }
        max_flow = max_flow + path_flow;
        new_flow=bfs();
    }
    fout<<max_flow<<"\n";
}


int main()
{
    fin >> M;
    read();
    maxflow();
    for(int i=1; i <= M; i++)
        for(int j= 1 + M; j <= 2 * M; j++)
        {
            if(capacitate[j][i])
                fout << i << " " << j - M << "\n";
        }
    return 0;
}