Cod sursa(job #2421573)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 15 mai 2019 11:45:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> a[1001];
int c[1001][1001],flux[10001][1001],n,m,viz[1001],coada[1001],s,d,minim,r;
int bfs()
{
    int i,prim,ultim,x,sw=0;
    for(i=1;i<=d;i++)
    {
        viz[i]=coada[i]=0;
    }
    viz[s]=-1;
    prim=ultim=1;
    coada[prim]=s;
    while(prim<=ultim)
    {
        x=coada[prim++];
        //cout<<x<<" ";
        for(i=0;i<a[x].size();i++)
        {
            if(viz[a[x][i]]==0 && c[x][a[x][i]]>flux[x][a[x][i]])
            {
                if(a[x][i]!=d)
                {
                    viz[a[x][i]]=x;
                    ultim++;
                    coada[ultim]=a[x][i];
                }
                else
                {
                    sw=1;
                }
            }
        }
    }
    return sw;
}
void dinic()
{
    int i,nod;
    while(bfs()!=0)
    {
        for(i=0;i<a[d].size();i++)
        {
            if(viz[a[d][i]]!=0 && c[a[d][i]][d]>flux[a[d][i]][d])
            {
                viz[d]=a[d][i];
                minim=0x7fffffff;;
                nod=d;
                while(nod!=s)
                {
                    if(minim>c[viz[nod]][nod]-flux[viz[nod]][nod])
                    {
                        minim=c[viz[nod]][nod]-flux[viz[nod]][nod];
                    }
                    nod=viz[nod];
                }
                if(minim>0)
                {
                    r=r+minim;
                    nod=d;
                    while(nod!=s)
                    {
                        flux[viz[nod]][nod]+=minim;
                        flux[nod][viz[nod]]-=minim;
                        nod=viz[nod];
                    }
                }
            }
        }
    }
}
int main()
{
    int i,x,y,j;
    f>>n;
    s=1;
    d=2*n+2;
    for(i=2;i<=n+1;i++)
    {
        f>>x>>y;
        c[s][i]=x;
        c[n+i][d]=y;
        a[s].push_back(i);
        a[i].push_back(s);
        a[n+i].push_back(d);
        a[d].push_back(n+i);
    }
    for(i=2;i<=n+1;i++)
    {
        for(j=n+2;j<=2*n+1;j++)
        {
            if(i!=j-n)
            {
                c[i][j]=1;
                a[i].push_back(j);
                a[j].push_back(i);
            }
        }
    }
    dinic();
    g<<r<<"\n";
    for(i=2;i<=n+1;i++)
    {
        for(j=n+2;j<=2*n+1;j++)
        {
            if(flux[i][j]==1)
            {
                g<<i-1<<" "<<j-n-1<<"\n";
            }
        }
    }
    return 0;
}