Cod sursa(job #2962264)

Utilizator Eronatedudu zzz Eronate Data 8 ianuarie 2023 03:25:02
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <bits/stdc++.h>
using namespace std;

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

vector<vector<int>>gr;
int flow[201][201];
int father[1002], visited[1002];

bool bfs(int n, int src, int dest)
{
    for(int i=1; i<dest; i++)
    {
        father[i] = 0;
        visited[i] = 0;
    }
    visited[dest]=0;
    queue<int> vertexes;
    vertexes.push(src);

    while(!vertexes.empty())
    {
        int currentNode = vertexes.front();
        vertexes.pop();
        for(auto extr2: gr[currentNode])
        {
                if(!visited[extr2] and flow[currentNode][extr2]>0) //daca nu am vizitat nodul extr2
                    //si capacitatea muchiei formata din nodul curent si extremitatea 2 permite trecerea flow-ului
                {

                    father[extr2] = currentNode;
                    if(extr2 == dest)
                        return true;
                    vertexes.push(extr2);
                    visited[extr2] = 1;
                }
        }

    }
    return false; //nu am gasit un drum de la sursa la destinatie, inseamna nu mai am drumuri si ca am ajuns la flux maxim
}

int fordFulkerson(int n, int src, int dest)
{
    int u, v, max_flow_for_route, currentNode;

    int srcAux = src, destAux = dest, fNode, finalFlow = 0;

    while(bfs(n, src, dest))
    {
        max_flow_for_route = INT_MAX - 1 ;
        srcAux = src;
        destAux = dest;
        while(destAux!=srcAux)
        {
            //calculez flow-ul maxim de transmis pe drumul gasit de bfs
            max_flow_for_route = min(max_flow_for_route, flow[father[destAux]][destAux]);
            destAux = father[destAux];
        }
        destAux = dest;
        srcAux = src;
        //acum updatez graful rezidual pe drumul gasit de bfs
        while(destAux!=srcAux)
        {
            fNode = father[destAux];
            flow[fNode][destAux] -= max_flow_for_route;    //muchia mea pe directia corecta va avea o capacitate mai mica de flow
            flow[destAux][fNode] += max_flow_for_route;    //muchia pe directia inversa va avea mai mult flow de dat
            //logic pt ca voi avea mai mult flow de extras
            destAux = fNode;
        }

        finalFlow += max_flow_for_route; //adun flow-ul drumului la flow-ul final
    }
    return finalFlow;
}
int main()
{
    int n,m,inNode,outNode,count=0;
    f>>n;
    int src = 0;
    int dst = 2*n +1;
    int delay = n;
    gr.resize(201);
    for(int i=1; i<=n; i++)
    {
        f>>outNode>>inNode;
        gr[src].push_back(i);
        gr[i+delay].push_back(dst);
        flow[src][i] = outNode;
        flow[i+delay][dst] = inNode;
    }
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
        {
            flow[i][j] = 1;
            gr[i].push_back(j);
            gr[j].push_back(i);
        }

    fordFulkerson(n,src,dst);

    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            if(flow[i][j] == 0)
                count++;
    g<<count<<'\n';
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            if(flow[i][j] == 0)
                g<<i<<' '<<j-delay<<endl;
    return 0;
}