Cod sursa(job #1332541)

Utilizator ThomasFMI Suditu Thomas Thomas Data 2 februarie 2015 10:10:27
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define NMax 205
#define inf 2100000000

ifstream f("harta.in");
ofstream g("harta.out");

int n,m;
vector<int> v[NMax];
queue<int> cd;

int C[NMax][NMax];
int F[NMax][NMax];
bool viz[NMax];
int ant[NMax];
int S,D;

bool BFS(int s)
{
    int i;

    for(i=S;i<=D;++i) viz[i] = false;
    viz[s] = true;
    cd.push(s);

    while(!cd.empty())
    {
        s = cd.front(); cd.pop();
        if(s!=D) for(i=0;i<v[s].size();++i) if(!viz[v[s][i]] && F[s][v[s][i]] < C[s][v[s][i]])
        {
            ant[v[s][i]] = s;
            viz[v[s][i]] = true;
            cd.push(v[s][i]);
        }
    }

    return viz[D];
}

int main()
{
    int i,j,a,b;

    f>>n;

    S = 0; D = 2*n+1;

    for(i=1;i<=n;++i)
    {
        f>>a>>b;
        v[S].push_back(i);
        v[i].push_back(S);
        v[n+i].push_back(D);
        v[D].push_back(n+i);

        C[S][i] += a;
        C[n+i][D] += b;
    }

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

    int newflow, s;

    while(BFS(S)) for(i=0;i<v[D].size();++i)
    {
        ant[D] = v[D][i];
        newflow = inf;
        s = D;
        while(s != S)
        {
            newflow = min( newflow , C[ant[s]][s] - F[ant[s]][s] );
            s = ant[s];
        }

        s = D;
        while(s != S)
        {
            F[ant[s]][s] += newflow;
            F[s][ant[s]] -= newflow;
            s = ant[s];
        }
    }

    int sol = 0;
    for(i=1;i<=n;++i) for(j=1;j<=n;++j) if(F[i][n+j] == 1) sol++; g<<sol<<"\n";
    for(i=1;i<=n;++i) for(j=1;j<=n;++j) if(F[i][n+j] == 1) g<<i<<" "<<j<<"\n";

    f.close();
    g.close();
    return 0;
}