Cod sursa(job #2961636)

Utilizator Anastasia7Anastasia Anastasia7 Data 6 ianuarie 2023 19:33:43
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

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

#define sz 201

vector<vector<int>> adj_list;
int capacity[sz][sz];
vector<int> parent;
int a,b,n,s,t;

bool BFS()
{
    vector<bool> viz(t);
    queue<int> coada;
    coada.push(s);
    viz[s]=true;
    parent[s]=-1;
    while(!coada.empty())
    {
        int u=coada.front();
        coada.pop();
        for(auto v:adj_list[u])
        {
            if(viz[v]==false && capacity[u][v]!=0)
            {
                parent[v]=u;
                if(v==t)
                    return true;
                viz[v]=true;
                coada.push(v);
            }
        }
    }
    return false;
}
int EdmondsKarp()
{
    long maxFlow=0;
    while(BFS()==true)
    {
        int u,v=t;
        int pathFlow=INT_MAX;
        while(v!=s)
        {
            u=parent[v];
            if(capacity[u][v]<pathFlow)
                pathFlow=capacity[u][v];
            v=parent[v];
        }
        v=t;
        while(v!=s)
        {
            u=parent[v];
            capacity[u][v]-=pathFlow;
            capacity[v][u]+=pathFlow;
            v=parent[v];
        }
        maxFlow+=pathFlow;
    }
    return maxFlow;
}

void afisare()
{
    fout<<EdmondsKarp()<<"\n";
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (capacity[j+n][i] == 1)
                fout<<i<<" "<<j<<endl;
}

void citire()
{
    fin>>n;
    s=0;
    t=2*n+1;
    parent.resize(2*n+1);
    adj_list.resize(sz);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            if(i!=j)
            {
                adj_list[i].push_back(j+n);
                adj_list[j+n].push_back(i);
                capacity[i][j+n]=1;
            }
        }
    for (int i=1; i<=n; i++)
    {
        int x,y;
        fin>>x>>y;
        adj_list[s].push_back(i);
        adj_list[i].push_back(s);
        capacity[s][i]=x;
        adj_list[t].push_back(i+n);
        adj_list[i+n].push_back(t);
        capacity[i+n][t]=y;
    }
    afisare();
}
int main()
{
    citire();
    return 0;
}