Cod sursa(job #2962131)

Utilizator deboradeleanuDebora Deleanu deboradeleanu Data 7 ianuarie 2023 20:12:42
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

vector<vector<int>> graf, rgraf;
vector<int> parent;

int n, dest, x,y;

void citire()
{
    fin >> n;
    //sursa=0;
    dest= 2 * n + 1;

    graf.resize(201);
    rgraf.resize(201, vector<int>(201));
    parent.resize(2 * n + 1);

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

    for(int i=1; i <= n; i++)
    {
        fin >> x >> y;
        graf[0].push_back(i);
        graf[i].push_back(0);

        graf[dest].push_back(i + n);
        graf[i + n].push_back(dest);

        rgraf[0][i]=x;
        rgraf[i + n][dest]=y;
    }


}

bool bfs()
{
    vector<bool> viz(2 * n + 1, false);
    queue<int> q;
    q.push(0);
    viz[0] = true;
    parent[0] = -1;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        for(auto ad: graf[nod])
            if(viz[ad] == false && rgraf[nod][ad] != 0)
            {
                parent[ad] = nod; //tine minte drumul
                if (ad == dest)
                    return true;
                viz[ad] = true;
                q.push(ad);
            }
    }
    return false;
}

int fordf()
{
    int flowtotal=0;
    while(bfs())
    {
        int u, v=dest, pathflow = INT_MAX;
        //sursa=0
        while(v != 0)
        {
            u = parent[v];
            if(rgraf[u][v] < pathflow)
                pathflow= rgraf[u][v];
            v = u;
        }
        v=dest;
        while(v != 0)
        {
            u = parent[v];
            rgraf[u][v] -= pathflow;
            rgraf[v][u] += pathflow;
            v = u;
        }
        flowtotal += pathflow;
    }
    return flowtotal;
}


int main()
{
    citire();
    fout << fordf()<<endl;

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

    return 0;
}