Cod sursa(job #1442269)

Utilizator simaghitaSima Gheorghe Eugen simaghita Data 24 mai 2015 21:04:30
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.72 kb
#include <iostream>
#include<vector>
#include<fstream>
#include<queue>
#define MAXN 210
using namespace std;
vector<int> L[MAXN];
int F[MAXN][MAXN],C[MAXN][MAXN],tata[MAXN],flux;
int sursa,dest,n,m;
queue<int> Q;
void initializare()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(i!=j)
            {
                L[i].push_back(j+n);
                L[j+n].push_back(i);
                C[i][j+n]=1;
            }
        }
    }
    sursa=2*n + 1;
    dest=2*n + 2;
}
void citire()
{
    int x,y;
    ifstream fin("harta.in");
    fin>>n;
    initializare();
    for(int i=1;i<=n;++i)
    {
        fin>>x>>y;
        L[sursa].push_back(i);
        L[i].push_back(sursa);
        C[sursa][i]=x;

        L[i+n].push_back(dest);
        L[dest].push_back(i+n);
        C[i+n][dest]=y;
    }
    fin.close();
//    for(int i=0;i<L[sursa].size();++i)
//        cout<<L[sursa][i]<<" ";
}
void reset()
{
     for(int i=1;i<=dest;++i)
        tata[i]=-1;
     tata[sursa]=0;
}
int BFS()
{
    reset();
    Q.push(sursa);
    while(!Q.empty())
    {
        int nod=Q.front();
        Q.pop();
        for(int i=0;i<L[nod].size();++i)
        {
            int k=L[nod][i];
            if(tata[k]==-1 && F[nod][k] < C[nod][k])
            {
                Q.push(k);
                tata[k]=nod;
            }
        }
    }
    if(tata[dest]==-1)
        return 0;
    return 1;
}
void fluxMaxim()
{

    while(BFS())
    {
        //parcurg vecinitii nodului destinatie
        for(int i=0;i<L[dest].size();++i)
        {
            int k=L[dest][i];
            if(F[k][dest] < C[k][dest])
            {
                int cost = C[k][dest] - F[k][dest];
                //calculez fluxul de pe acest drum
                while(tata[k]!=0)
                {
                    int t=tata[k];
                    cost= min(cost, C[t][k] - F[t][k]);
                    k=t;
                }
                flux+=cost;

                k=L[dest][i];
                //actualizez fluxul
                F[dest][k]-=cost;
                F[k][dest]+=cost;

                while(tata[k]!=0)
                {
                    int t=tata[k];
                    F[t][k]+=cost;
                    F[k][t]-=cost;
                    k=t;
                }

            }
        }
    }
}
void solve()
{
    fluxMaxim();
    ofstream fout("harta.out");
    fout<<flux<<"\n";
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            if(i!=j && F[i][j+n]==1)
                fout<<i<<" "<<j<<"\n";
        }
    fout.close();

}
int main()
{
    citire();
    solve();
    return 0;
}