Cod sursa(job #3363784)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 22 august 2026 17:51:57
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> v[1009];
bool viz[1009];
queue <int> q;
int N;
int ans[10009];
int tata[1009], r[1009][1009], s, d, sol=0, n;
bool bfs ()
{
    for (int i=1; i<=N; i++)
        viz[i]=0, tata[i]=0;
    q.push(s);
    viz[s]=1;
    while (!q.empty())
    {
        int x=q.front();
        q.pop();
        for (auto y:v[x])
        {
            if (!viz[y] && r[x][y]>0)
            {
                viz[y]=1;
                tata[y]=x;
                q.push(y);
            }
        }
    }
    return viz[d];
}
void flux_maxim ()
{
    int flow=0;
    while (bfs())
    {
        for (auto y:v[d])
        {
            if ((tata[y]!=0 || y==s) && r[y][d]>0)
            {
                flow=r[y][d];
                for (int j=y; j!=s; j=tata[j])
                {
                    flow=min (flow, r[tata[j]][j]);
                    if (!flow)
                        break;
                }
                if (flow)
                {
                    r[y][d]-=flow;
                    r[d][y]+=flow;
                    for (int j=y; j!=s; j=tata[j])
                    {
                        r[tata[j]][j]-=flow;
                        r[j][tata[j]]+=flow;
                    }
                    sol+=flow;
                }
            }
        }
    }
}
signed main ()
{
    int m;
    f >> n;
    s=2*n+1, d=2*n+2, N=2*n+2;
    for (int j=1; j<=n; j++)
    {
        int a, b;
        f >> a >> b;
        v[s].push_back(j);
        v[j].push_back(s);
        r[s][j]+=a;
        v[d].push_back(j+n);
        v[j+n].push_back(d);
        r[j+n][d]+=b;
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (i!=j)
            {
                v[i].push_back(j+n);
                v[j+n].push_back(i);
                r[i][j+n]=1;
                r[j+n][i]=0;
            }
        }
    }
    flux_maxim();
    vector <pair <int, int> > ans;
    g << sol<<'\n';
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (i!=j && r[i][j+n]==0)
            ans.push_back ({i, j});
        }
    }
    for (auto p:ans)
    {
        g << p.first << ' ' << p.second<<'\n';
    }
}