Cod sursa(job #3364367)

Utilizator CarenaMironov Cezar Luca Carena Data 2 septembrie 2026 11:50:40
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX=2e2+5, INF=1e9;
int n, dist[NMAX], ptr[NMAX];
vector<int> adj[NMAX];

struct edge{int u, v, cap, flow;};
vector<edge> ve;

void add_edge(int u, int v, int c)
{
    ve.push_back({u, v, c, 0});
    adj[u].push_back(ve.size()-1);
    
    ve.push_back({v, u, 0, 0});
    adj[v].push_back(ve.size()-1);
}

bool BFS(int s, int t)
{
    for(int i=0;i<=2*n+1;i++)
        dist[i]=INF;
    dist[s]=0;
    
    queue<int> q; q.push(s);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(auto i:adj[u])
            if(ve[i].flow<ve[i].cap && dist[ve[i].v]==INF)
            {
                dist[ve[i].v]=dist[u]+1;
                q.push(ve[i].v);
            }
    }
    
    return dist[t]<INF;
}

int DFS(int u, int f, int t)
{
    if(u==t || f==0)
        return f;
    for(;ptr[u]<adj[u].size();ptr[u]++)
    {
        int id=adj[u][ptr[u]];
        edge e=ve[id];
        if(dist[e.v]!=dist[u]+1)
            continue;
        int pf=DFS(e.v, min(f, e.cap-e.flow), t);
        if(pf>0)
        {
            ve[id].flow+=pf;
            ve[id^1].flow-=pf;
            return pf;
        }
    }
    return 0;
}

int flow(int s, int t)
{
    int ans=0;
    while(BFS(s, t))
    {
        for(int i=0;i<=2*n+1;i++)
            ptr[i]=0;
        while(true)
        {
            int pf=DFS(s, INF, t);
            ans+=pf;
            if(!pf)
                break;
        }
    }
    return ans;
}

int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
    {
        int x, y; in>>x>>y;
        add_edge(0, 2*i, x);
        add_edge(2*i+1, 1, y);
    }
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                add_edge(2*i, 2*j+1, 1);
    
    out<<flow(0, 1)<<'\n';
    for(auto e:ve)
        if(e.u!=0 && e.v!=1 && e.flow==1)
            out<<e.u/2<<" "<<e.v/2<<'\n';
    return 0;
}