Cod sursa(job #1508929)

Utilizator mariusn01Marius Nicoli mariusn01 Data 23 octombrie 2015 10:25:07
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>
#include <vector>
#include <deque>
#define DIM 102
using namespace std;

int C[2*DIM][2*DIM], F[2*DIM][2*DIM], U[2*DIM], T[2*DIM], minim;
vector<int> L[2*DIM];
deque<int> q;
int in, out, i, j, p, u, n, nod, vecin, flux;

int bfs() {
    int gasit = 0;

    for (int i=0;i<=2*n+1;i++)
        U[i] = 0;
    U[0] = 1;
    q.push_back(0);
    while (!q.empty()) {
        nod = q.front();
        for (int i=0;i<L[nod].size();i++) {
            int vecin = L[nod][i];
            if (U[vecin] == 0 && C[nod][vecin] > F[nod][vecin]) {
                q.push_back(vecin);
                U[vecin] = 1;
                T[vecin] = nod;
                if (vecin == 2*n+1)
                    gasit = 1;
            }

        }
        q.pop_front();

    }
    return gasit;

}

int main () {
    ifstream fin("harta.in");
    ofstream fout("harta.out");

    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>out>>in;
        C[0][i] = out;
        L[0].push_back(i);
        L[i].push_back(0);
        C[n+i][2*n+1] = in;
        L[n+i].push_back(2*n+1);
        L[2*n+1].push_back(n+i);
    }

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

    while (bfs()) {
        for (int i=0;i<L[2*n+1].size();i++) {
            p = L[2*n+1][i];
            if (C[p][2*n+1] > F[p][2*n+1] && U[p] == 1) {
                minim = C[p][2*n+1] - F[p][2*n+1];
                u = p;
                while (u!= 0) {
                    if ( C[ T[u] ][u] - F[ T[u] ][u] < minim) {
                        minim = C[ T[u] ][u] - F[ T[u] ][u];
                    }
                    u = T[u];
                }
                flux += minim;

                F[p][2*n+1] += minim;
                F[2*n+1][p] -= minim;

                u = p;
                while (u != 0) {
                    F[ T[u] ][u] += minim;
                    F[ u ][ T[u] ] -= minim;
                    u = T[u];
                }

            }

        }

    }
    fout<<flux<<"\n";
    for (i=1;i<=n;i++)
        for (j=n+1;j<=2*n;j++)
            if (F[i][j] == 1) {
                fout<<i<<" "<<j-n<<"\n";
            }

    return 0;
}