Cod sursa(job #2710945)

Utilizator adiaioanaAdia R. adiaioana Data 23 februarie 2021 14:21:57
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
int flow, n, s_in,s_out, g[1010][1010], T[1010], q[1010];
inline void scan();
bool bfs();
int main()
{
    scan();
    while(bfs())
    {
        for(int nod=2*n+1; nod!=0; nod=T[nod])
            g[T[nod]][nod]--, g[nod][T[nod]]++;
    }
    if(flow<s_in)
        cout<<-1<<'\n';
    else{
        cout<<flow<<'\n';
        for(int i=1; i<=n; ++i)
            for(int j=1+n; j<=2*n; ++j)
                if(g[j][i])
                    cout<<i<<' '<<j-n<<'\n';
    }
    return 0;
}

inline void scan()
{
    int x,y;
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>x>>y;
        s_in+=x;
        s_out+=y;
        g[0][i]=x;
        g[i+n][2*n+1]=y;
    }
    if(s_in!=s_out)
    {
        cout<<-1<<'\n';
        exit(0);
    }
    for(int i=1; i<=n; ++i)
        for(int j=n+1; j<=2*n; ++j)
            if(j-i!=n)
                g[i][j]=1;
}

bool bfs()
{
    for(int i=0; i<=2*n+1; ++i)
        T[i]=-1, q[i]=0;

    int head=0, tail=0, nod=0;
    q[0]=0; T[0]=0;
    for(head=tail=0; head<=tail; ++head)
    {
        nod=q[head];
        for(int j=1; j<=2*n+1; ++j)
            if(g[nod][j] && T[j]==-1)
            {
                T[j]=nod;
                q[++tail]=j;
                if(j==2*n+1)
                {
                    flow++;
                    return 1;
                }
            }
    }
    return 0;
}