Cod sursa(job #2628412)

Utilizator betybety bety bety Data 15 iunie 2020 20:25:15
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
const int inf=2e9+7;
vector<int> vec[105];
int in[105],out[105];
int c[105][105];
int pred[105];
queue<int> q;
int main()
{
    int n,si=0,so=0;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>out[i]>>in[i];
        so+=out[i];
        si+=in[i];
    }
    if(so!=si)
    {
        cout<<-1<<'\n';
        return 0;
    }
    for(int i=1;i<=n;++i)
    {
        vec[i].push_back(i+n);
        vec[i+n].push_back(i);
        c[i+n][i]=inf;
        vec[0].push_back(i);
        vec[i].push_back(0);
        c[0][i]=in[i];
        vec[i+n].push_back(2*n+1);
        vec[2*n+1].push_back(i+n);
        c[i+n][2*n+1]=out[i];
    }
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    if(i!=j)
    {
        vec[i].push_back(j+n);
        vec[j+n].push_back(i);
        c[i][j+n]=1;
    }
    int flow=0,ads;
    do
    {
        for(int i=1;i<=2*n+1;++i)
            pred[i]=-1;
        pred[0]=-2;
        q.push(0);
        while(!q.empty())
        {
            int x=q.front(); q.pop();
            for(int y:vec[x])
            if(pred[y]==-1 and c[x][y]>0)
            {
                pred[y]=x;
                q.push(y);
            }
        }
        if(pred[2*n+1]>=0)
        for(int t=n+1;t<=2*n;++t)
        if(pred[t]>=0 and c[t][2*n+1]>0)
        {
            ads=c[t][2*n+1];
            for(int k=t;pred[k]>=0;k=pred[k])
                ads=min(ads,c[pred[k]][k]);
            if(ads<=0) continue;
            c[t][2*n+1]-=ads;
            c[2*n+1][t]+=ads;
            for(int k=t;pred[k]>=0;k=pred[k])
            {
                c[pred[k]][k]-=ads;
                c[k][pred[k]]+=ads;
            }
            flow+=ads;
        }
    }while(pred[2*n+1]>=0);
    if(flow!=si)
    {
        cout<<-1<<'\n';
        return 0;
    }
    cout<<flow<<'\n';
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    if(i!=j and c[i][j+n]==0)
        cout<<i<<' '<<j<<'\n';
    return 0;
}