Cod sursa(job #1690487)

Utilizator sucureiSucureiRobert sucurei Data 15 aprilie 2016 09:59:22
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> G[205];
int Source,Sink,C[205][205],TT[205],F[205][205],N;
queue <int> Q;
bool Use[205];
void Read()
{
    f>>N;
    Sink=2*N+1;
    for(int i=1;i<=N;i++)
    {
        int x,y;
        f>>x>>y;
        C[Source][i]=x;
        C[i+N][Sink]=y;
    }
    for(int i=1;i<=N;i++)
    {
        G[Source].push_back(i);
        G[i].push_back(Source);
        G[i+N].push_back(Sink);
        G[Sink].push_back(i+N);
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(i!=j)
            {
                C[i][j+N]=1;
                G[i].push_back(j+N);
                G[j+N].push_back(i);
            }
}
int BFS()
{
    memset(Use,0,sizeof(Use));
    Q.push(Source); Use[Source] = 1;

    while(!Q.empty())
    {
        int Node = Q. front(); Q. pop();

        if(Node == N) continue;

        for(unsigned int i = 0; i < G[Node].size(); ++i)
        {
            int Neighbour = G[Node][i];

            if(!Use[Neighbour] && C[Node][Neighbour]-F[Node][Neighbour]>0)
            {
                TT[Neighbour] = Node;
                Q.push(Neighbour);
                Use[Neighbour] = 1;
            }
        }
    }

return Use[N];

}

void Solve()
{
    int number=N;
    N=Sink;
    while(BFS())
    {

        for(unsigned int k = 0; k<G[N].size(); ++k)
        {

        int Vecin = G[N][k];

        if(!Use[Vecin] || C[Vecin][N]-F[Vecin][N] == 0) continue;

        TT[N] = Vecin;

        int Fmin = 120000;

        for(int i = N ; i != 0 ; i = TT[i])
            Fmin = min(Fmin,C[TT[i]][i]-F[TT[i]][i]);


        for(int i = N ; i != 0 ; i = TT[i])
        {
            F[TT[i]][i] += Fmin;
            F[i][TT[i]] -= Fmin;
        }

        }
    }
    int ans=0;
    N=number;
    for(int i=1;i<=N;i++)
        for(int j=N+1;j<=2*N;j++)
            if(F[i][j]!=0)
                ++ans;
        g<<ans<<"\n";
        for(int i=1;i<=N;i++)
            for(int j=N+1;j<=2*N;j++)
                if(F[i][j]!=0)
                    g<<i<<" "<<j-N<<"\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}