Cod sursa(job #3188991)

Utilizator FunZoneLutu Adrian-Catalin FunZone Data 4 ianuarie 2024 12:30:20
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>

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

int n, capacitati[205][205];

vector<vector<int>> adj(205);

int bfs(int s,int d,vector<int> &parent)
{
    fill(parent.begin(),parent.end(),-1);
    queue<pair<int,int>> q;
    q.push(pair(s,999999));

    while(!q.empty())
    {
        int curr = q.front().first;
        int flow = q.front().second;
        q.pop();

        for(int next : adj[curr])
        {
            if(parent[next] == -1 && capacitati[curr][next])
                {
                    parent[next] = curr;

                    int new_flow = min(flow,capacitati[curr][next]);

                    if(next == d)
                        return new_flow;
                    
                    q.push(pair(next,new_flow));
                }
        }
    }

    return 0;
}


int maxflow(int s,int d)
{
    int flow = 0;
    vector<int> parent(2*n+2);
    

    int new_flow;

    while(new_flow = bfs(s,d,parent))
    {
        flow += new_flow;
        int curr = d;
        while(curr != s)
        {
            int prev = parent[curr];
            capacitati[prev][curr] -= new_flow;
            capacitati[curr][prev] += new_flow;
            curr = prev;
        }

    }

    return flow;
}

int main()
{
    fin>>n;

    for(int i = 1;i<=n;i++)
    {
        fin>>capacitati[0][i]>>capacitati[n+i][2*n+1];
        adj[0].emplace_back(i);
        adj[i].emplace_back(0);
        adj[n+i].emplace_back(2*n+1);
        adj[2*n+1].emplace_back(n+i);
    }

    for(int i = 1;i<= n;i++)
        for(int j = n+1;j<=2*n;j++)
            if(i+n != j)
            {
                capacitati[i][j] = 1;
                adj[i].emplace_back(j);
                adj[j].emplace_back(i);
            }
    fout<<maxflow(0,2*n+1)<<endl;

    for(int i = 1;i<= n;i++)
        for(int j = n+1;j<=2*n;j++)
            if(capacitati[i][j] == 0 && i+n != j)
                fout<<i<<" "<<j-n<<endl;   
    return 0;
}