Cod sursa(job #2957307)

Utilizator EduardSanduSandu Eduard Alexandru EduardSandu Data 22 decembrie 2022 11:58:39
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>
using namespace std;

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

int capacity[205][205],n,m,flow,max_flow;
vector<int> visited,parent;
bool bfs()
{
    fill(visited.begin(), visited.end(), 0);
    fill(parent.begin(), parent.end(), 0);

    visited[0] = 1;
    parent[0] = -1;
    queue<int> q;
    q.push(0);

    while(!q.empty())
    {
        int nod = q.front();

        q.pop();

        if(nod == 2*n+1)
            return true;

        for(int i=1; i<=2*n+1; i++)
        {
            if(!visited[i] && capacity[nod][i] > 0)
            {
                q.push(i);
                parent[i] = nod;
                visited[i] = 1;
            }
        }
    }

    return false;


}

int main()
{
    int a,b,c;
    fin>>n;
    visited.resize(2*n+2, 0);
    parent.resize(2*n+2, 0);
    //setam capacitatile pentru intrare si iesire

    for(int i=1; i<=n; i++)
    {
        fin>>a>>b;
        capacity[0][i] = a;
        capacity[n+i][2*n+1] = b;
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            capacity[i][n+j] = 1;
        }
        capacity[i][n+i] = 0;
    }

    int reusit = bfs();

    while(reusit)
    {
        for(int i=1; i<=n; i++)
        {
            if(visited[n+i])
            {
                parent[2*n+1] = n+i;
                flow = INT_MAX;
                for(int j=2*n+1; j!=0; j=parent[j])
                {
                    flow=min(flow, capacity[parent[j]][j]);
                }
                if(flow != 0)
                {
                    for(int j=2*n+1; j!=0; j=parent[j])
                    {
                        capacity[parent[j]][j] -= flow;
                        capacity[j][parent[j]] += flow;
                    }
                    max_flow += flow;
                }
            }
        }
        reusit = bfs();
    }

    fout<<max_flow<<'\n';

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i != j && capacity[i][n+j] == 0)
                fout<<i<<' '<<j<<'\n';
        }
    }

    return 0;
}