Cod sursa(job #2967182)

Utilizator tm123321teo mihailescu tm123321 Data 19 ianuarie 2023 10:26:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define INF 9999999

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

//  O(N*M),N-nr varfuri, M-nr muchii
vector<vector<int>>la;
int capacitate[202][202];
int tata[202];
int n;
int BFS()
{
    queue<pair<int,int>> q;
    for(int i=0; i<=2*n+1; i++)
    {
        tata[i]=-1;
    }
    q.push({0,INF});
    tata[0]=-2;
    while(!q.empty())
    {
        int u=q.front().first;
        int flow=q.front().second;
        q.pop();
        for(auto v:la[u])
        {
            if(tata[v]==-1 && capacitate[u][v]>0)
            {
                tata[v]=u;
                int new_flow=min(flow,capacitate[u][v]);
                if(v==2*n+1)
                    return new_flow;
                q.push({v,new_flow});
            }
        }
    }
    return 0;
}
int calc()
{  int flow,maxflow=0;
    while(flow=BFS())
    {
        maxflow+=flow;
        int cur=2*n+1;
        //revizuim flux lant
        while(cur!=0)
        {
            int prev=tata[cur];
            capacitate[cur][prev]+=flow;
            capacitate[prev][cur]-=flow;
            cur=prev;
        }
    }
    return maxflow;

}
int main()
{


    f>>n;
    la.resize(2*n+2);
    for(int i=1; i<=n; i++)
    {
        int x,y;
        f>>x>>y;

        la[0].push_back(i);// ad muchii cu cap x
        la[i].push_back(0);
        capacitate[0][i]=x;

        capacitate[n+i][2*n+1]=y;//ad muchii cu cap y
        la[n+i].push_back(2*n+1);
        la[2*n+1].push_back(n+i);
        for(int j=n+1; j<=2*n; j++)
        {

            if(j-i==n)// ad muc cu cap 1 si i!=j
                continue;
            capacitate[i][j]=1;
            la[i].push_back(j);
            la[j].push_back(i);
        }
    }
    g<<calc()<<'\n';
    for(int i=1; i<=n; i++)
        for(int j=n+1; j<=2*n; j++)
            if(capacitate[j][i]==1)
            {
                g<<i<<" "<<j-n<<'\n';
            }


}