Cod sursa(job #1002948)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 29 septembrie 2013 13:09:30
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define NM 210

using namespace std;

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

int N, i, j;
int S, D;
vector<int> G[NM];
vector< pair<int, int> > ANS;
int Cap[NM][NM], Flow[NM][NM];
int T[NM];
bool V[NM];
queue<int> Q;

bool BF ()
{
    memset(V, 0, sizeof(V));
    Q.push(S);
    V[S]=1;

    int node;
    vector<int>::iterator it;

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

        if (node==D) continue;

        for (it=G[node].begin(); it!=G[node].end(); ++it)
            if (!V[*it] && Flow[node][*it]<Cap[node][*it])
            {
                V[*it]=1;
                T[*it]=node;
                Q.push(*it);
            }
    }

    return V[D];
}

int main ()
{
    f >> N;
    S=0; D=2*N+1;

    for (i=1; i<=N; i++)
    {
        G[S].push_back(i);
        G[i].push_back(S);
        G[D].push_back(i+N);
        G[i+N].push_back(D);

        f >> Cap[S][i] >> Cap[i+N][D];

        for (j=1; j<=N; j++)
            if (i!=j)
            {
                G[i].push_back(j+N);
                G[j+N].push_back(i);
                Cap[i][j+N]=1;
            }
    }

    while (BF())
        for (vector<int>::iterator it=G[D].begin(); it!=G[D].end(); ++it)
            if (V[*it]==1 && Flow[*it][D]<Cap[*it][D])
            {
                T[D]=*it;
                int FMIN=0x3f3f3f3f;

                for (i=D; i!=S; i=T[i])
                    FMIN=min(FMIN, Cap[T[i]][i]-Flow[T[i]][i]);

                for (i=D; i!=S; i=T[i])
                {
                    Flow[T[i]][i]+=FMIN;
                    Flow[i][T[i]]-=FMIN;
                }
            }

    for (i=1; i<=N; i++)
        for (j=1; j<=N; j++)
            if (Flow[i][j+N]==1)
                ANS.push_back(make_pair(i, j));

    g << ANS.size() << '\n';
    for (i=0; i<ANS.size(); i++)
        g << ANS[i].first << ' ' << ANS[i].second << '\n';

    f.close();
    g.close();

    return 0;
}