Cod sursa(job #2666877)

Utilizator betybety bety bety Data 2 noiembrie 2020 16:10:43
Problema Taramul Nicaieri Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
vector<int> vec[205];
int c[205][205];
int last[205];
queue<int> q;
int main()
{
    int n,x,y,s=0;
    in>>n;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j) if(i!=j)
    {
        c[i][j+n]=1;
        vec[i].push_back(j+n);
        vec[j+n].push_back(i);
    }
    for(int i=1;i<=n;++i)
    {
        c[i+n][i]=n;
        vec[i].push_back(i+n);
        vec[i+n].push_back(i);
        in>>x>>y;
        s+=x;
        c[0][i]=x;
        vec[0].push_back(i);
        vec[i].push_back(0);
        c[i+n][2*n+1]=y;
        vec[i+n].push_back(2*n+1);
        vec[2*n+1].push_back(i+n);
    }
    do
    {
        last[0]=-2;
        for(int i=1;i<=2*n+1;++i)
            last[i]=-1;
        q.push(0);
        while(!q.empty())
        {
            int x=q.front(); q.pop();
            for(int y:vec[x])
            if(last[y]==-1 and c[x][y]>0)
            {
                last[y]=x;
                q.push(y);
            }
        }
        if(last[2*n+1]>=0)
        for(int x:vec[2*n+1])
        if(c[x][2*n+1]>0 and last[x]>=0)
        {
            int minim=c[x][2*n+1];
            for(int u=x;last[u]>=0;u=last[u])
                minim=min(minim,c[last[u]][u]);
            if(minim==0) continue;
            c[x][2*n+1]-=minim;
            c[2*n+1][x]+=minim;
            for(int u=x;last[u]>=0;u=last[u])
            {
                c[last[u]][u]-=minim;
                c[u][last[u]]+=minim;
            }
        }
    }while(last[2*n+1]>=0);
    out<<s<<'\n';
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    if(i!=j and c[i][j+n]==0)
        out<<i<<' '<<j<<'\n';
    return 0;
}