Cod sursa(job #1507824)

Utilizator TibixbAndrei Tiberiu Tibixb Data 21 octombrie 2015 22:28:53
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include<fstream>
#include<vector>
#include<bitset>
#include<deque>
using namespace std;
vector <int> L[105];
bitset<105> u;
deque <int> q;
pair<int, int> sol[103];
int T[105], n, i, x, y, C[105][105], j, nod, ok, minim, vecin, F[105][105], nr, nrsol;
int bfs()
{
    q.clear();
    u.reset();
    q.push_back(101);
    u[101]=1;
    ok=0;
    while(!q.empty())
    {
        nod=*q.begin();
        if(nod==102)
        {
            ok=1;
            break;
        }
        for(int i=0; i<L[nod].size(); i++)
        {
            vecin=L[nod][i];
            if(u[vecin]==0 && C[nod][vecin]-F[nod][vecin]>0)
            {
                q.push_back(vecin);
                T[vecin]=nod;
                u[vecin]=1;
            }
        }
        q.pop_front();
    }
    return ok;
}
ifstream in("harta.in");
ofstream out("harta.out");
int main()
{
    in>>n;
    for(i=1; i<=n; i++)
    {
        in>>x>>y;
        L[101].push_back(i);
        L[i].push_back(101);
        L[102].push_back(i+n);
        L[i+n].push_back(102);
        C[101][i]=x;
        C[i+n][102]=y;
        for(j=n+1; j<=2*n; j++)
        {
            if(j!=i+n)
            {
                L[i].push_back(j);
                L[j].push_back(i);
                C[i][j]=1;
            }
        }
        nrsol+=x;
    }
    while(bfs())
    {
        for(i=0; i<L[102].size(); i++)
        {
            nod=L[102][i];
            if(u[nod]==1 && C[nod][102]-F[nod][102]>0)
            {
                minim=C[nod][102]-F[nod][102];
                for(; T[nod]!=0 && minim!=0; nod=T[nod])
                {
                    minim=min(minim, C[T[nod]][nod]-F[T[nod]][nod]);
                }
                if(minim!=0)
                {
                    nod=L[102][i];
                    F[nod][102]+=minim;
                    F[102][nod]-=minim;
                    for(; T[nod]!=0 && minim!=0; nod=T[nod])
                    {
                        if(T[nod]>=1 && T[nod]<=n)
                        {
                            sol[++nr].first=T[nod];
                            sol[nr].second=nod-n;
                        }
                        F[T[nod]][nod]+=minim;
                        F[nod][T[nod]]-=minim;
                    }
                }

            }
        }
    }
    out<<nrsol<<"\n";
    for(i=nr; i>=nr-nrsol+1; i--)
        out<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;
}