Cod sursa(job #2962148)

Utilizator vlanderovlad rosu vlandero Data 7 ianuarie 2023 20:54:27
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<vector<int>> residualGraph;
vector<vector<int>> adjList;
vector<int> tt;
vector<int> viz;
int n, N;

bool bfs()
{
    for(int i = 0; i <= N; ++i)
    {
        tt[i] = 0;
        viz[i] = 0;
    }
    tt[0] = -1;
    viz[0] = 1;
    queue<int> q;
    q.push(0);
    while(!q.empty())
    {
        int crt = q.front();
        q.pop();
        for(int node : adjList[crt])
        {
            if(viz[node] == 0 && residualGraph[crt][node] > 0)
            {
                q.push(node);
                viz[node] = 1;
                tt[node] = crt;
                if(node == N)
                    return true;
            }
        }
    }
    return false;
}

int getFlow()
{
    int flow = INT_MAX;
    int i = N;
    while(i != 0)
    {
        flow = min(flow, residualGraph[tt[i]][i]);
        i = tt[i];
    }
    return flow;
}

void updateResidual(int flow)
{
    int i = N;
    while(i != 0)
    {
        residualGraph[i][tt[i]] += flow;
        residualGraph[tt[i]][i] -= flow;
        i = tt[i];
    }
}


int main()
{
    fin>>n;
    N = 2 * n + 1;
    tt.resize(N + 1);
    viz.resize(N + 1);
    residualGraph.resize(N + 1, vector<int>(N + 1, 0));
    adjList.resize(N + 1);
    int x, y;
    int res = 0;
    for(int i = 1; i <= n; ++i)
    {
        fin>>x>>y;
        residualGraph[0][i] = x;
        residualGraph[i + n][N] = y;
        adjList[0].push_back(i);
        adjList[i].push_back(0);
        adjList[i + n].push_back(N);
        adjList[N].push_back(i + n);
    }

    for(int i=1; i <= n; i++)
        for(int j= 1 + n; j <= 2 * n; j++)
            if(i != j- n)
            {
                residualGraph[i][j]=1;
                adjList[i].push_back(j);
                adjList[j].push_back(i);
            }

    while(bfs())
    {
        int flow = getFlow();
        res += flow;
        updateResidual(flow);

    }
    fout<<res<<'\n';
    for(int i=1; i <= n; i++)
        for(int j= 1 + n; j <= 2 * n; j++)
            if(residualGraph[j][i])
                fout << i << " " << j - n << "\n";

    return 0;
}