Cod sursa(job #2960856)

Utilizator adamemi02emanuel adam adamemi02 Data 5 ianuarie 2023 01:22:56
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.27 kb
#include <fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
bool exists[1005];
int pre[1005],C[1005][1005],flux[1005][1005],n;
vector <int> adj[1005];
queue <int> coada;

void bfs()
{
    int nod,vecin,i;
    for(i=0;i<=2*n+1;i++) {exists[i]=0; pre[i]=0;}
    exists[0]=1;
    pre[0]=-1;
    coada.push(0);
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop();
        for(i=0;i<adj[nod].size();i++)
        {
            vecin=adj[nod][i];
            if (!exists[vecin] && C[nod][vecin]> flux[nod][vecin])
            {
                exists[vecin]=1;
                pre[vecin]=nod;
                coada.push(vecin);
            }
        }
    }
}

int main()
{
    int i,m,fluxtotal=0,mini,x,y,c,nod,urm,s,d;
    cin>>n;
    s=0;
    d=2*n+1;
    for(i=1;i<=n;i++)
    {
        cin>>x>>y;

        C[s][i]=y;
        C[n+i][d]=x;

        adj[s].push_back(i);
        adj[i].push_back(s);

        adj[d].push_back(n+i);
        adj[n+i].push_back(d);

        for(int j=1;j<=n;j++)
            if(i!=j){
                C[i][n+j]=1;
                adj[i].push_back(n+j);
                adj[n+j].push_back(i);
            }
    }


    while(true)
    {
        bfs();
        if(exists[d]==0) break;
        for(i=0;i<adj[d].size();i++)
            if (exists[adj[d][i]] && C[adj[d][i]][d]>flux[adj[d][i]][d])
            {
                nod=adj[d][i];
                urm=d;
                mini=C[nod][urm]-flux[nod][urm];
                while(nod>=0)
                {
                    mini=min(mini, C[nod][urm]-flux[nod][urm]);
                    urm=nod;
                    nod=pre[nod];
                }
                if(mini)
                {
                    nod=adj[d][i];
                    urm=d;
                    while(nod>=0)
                    {
                        flux[nod][urm]+=mini;
                        flux[urm][nod]-=mini;
                        urm=nod;
                        nod=pre[nod];
                    }
                }
                fluxtotal=fluxtotal+mini;
            }
    }
    cout<<fluxtotal<<'\n';
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            if(flux[i][j]==1)
                cout<<j-n<<" "<<i<<'\n';

    return 0;
}