Cod sursa(job #2617278)

Utilizator betybety bety bety Data 21 mai 2020 12:52:11
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
const int lim=205;
vector<int> vec[lim];
int c[lim][lim];
int pred[lim];
queue<int> q;
int main()
{
    int n,out,in,nr,m=0;
    cin>>n;
    nr=2*n+1;
    for(int i=1;i<=n;++i)
    {
        cin>>out>>in;
        vec[0].push_back(i); vec[i].push_back(0);
        vec[i+n].push_back(nr); vec[nr].push_back(i+n);
        c[0][i]=in;
        c[i+n][nr]=out;
        m+=out;
    }
    for(int i=1;i<=n;++i)
    for(int j=n+1;j<nr;++j)
    if(i+n!=j)
    {
        vec[i].push_back(j); vec[j].push_back(i);
        c[i][j]=1;
    }
    cout<<m<<'\n';
    int flow=0,ads;
    do
    {
        for(int i=1;i<=nr;++i)
            pred[i]=0;
        pred[0]=-1;
        q.push(0);
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(auto y:vec[x])
            if(c[x][y]>0 and pred[y]==0)
            {
                pred[y]=x;
                q.push(y);
            }
        }
        if(pred[nr]>0)
        for(auto t:vec[nr])
        if(pred[t]>0 and c[t][nr]>0)
        {
            ads=c[t][nr];
            for(int k=t;pred[k]>0;k=pred[k])
                ads=min(ads,c[pred[k]][k]);
            c[t][nr]-=ads;
            c[nr][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[nr]>0);
    for(int i=1;i<=n;++i)
    for(int j=n+1;j<nr;++j)
    if(i+n!=j and c[i][j]==0)
        cout<<i<<' '<<j-n<<'\n';
    return 0;
}