Cod sursa(job #2156070)

Utilizator Y0da1NUME JMECHER Y0da1 Data 8 martie 2018 14:05:57
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

#define maxn 105
using namespace std;
const int oo = 2e9;

int N;
int cap [2 * maxn][2 * maxn];
int flow [2 * maxn][2 * maxn];
int viz[2 * maxn];
int T[2 * maxn];

int source, sink;
vector <int> G [2 * maxn];
queue <int> Q;

void clear_q()
{
    while (!Q.empty())
        Q.pop();
    return;
}

int befeu()
{
    clear_q();
    for(int i = 0; i <= 2 * maxn; ++i)
        viz[i] = 0;
    viz[source] = 1;
    Q.push(source);
    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        if(nod == sink)
            continue;
        for(int j = 0; j < G[nod].size(); ++j)
        {
            int vecin = G[nod][j];
            if(cap[nod][vecin] == flow[nod][vecin] || viz[vecin])
                continue;
            viz[vecin] = 1;
            T[vecin] = nod;
            Q.push(vecin);
            //if(vecin == N)  ///am ajuns la sink
                //return 1;
        }
    }
    return viz[sink];
}
int main()
{
    ifstream in ("harta.in");
    ofstream out ("harta.out");
    in >> N;
    source = 0;
    sink = 2 * N + 1;

    for (int i = 1; i <= N; ++i)
    {
        int x, y;
        in>>x>>y;

        G[source].push_back(i);
        G[i].push_back(source);
        cap[source][i] = x;

        G[sink].push_back(N + i);
        G[N + i].push_back(sink);
        cap[N + i][sink] = y;

        for(int j = 1; j <= N; ++j)
        {
            if(j == i) continue;
            G[i].push_back(j + N);
            G[j + N].push_back(i);
            cap[i][j + N] = 1;
        }
    }
    int maxflow = 0;
    while(befeu())
    {
        int cur;
        for(int i = 0; i < G[sink].size(); ++i)
        {
            cur = G[sink][i];
            if (flow[cur][sink] == cap[cur][sink] || !viz[cur])
                continue;
            T[sink] = cur;

            int minim = oo;
            for (cur = sink; cur != source; cur = T[cur])
                minim = min(minim, cap[T[cur]][cur] - flow[T[cur]][cur]);    ///gasim bottleneckul

            //updatam fluxul maxim cu minim unitati
            for (cur = sink; cur != source; cur = T[cur])
            {
                flow[T[cur]][cur] += minim;
                flow[cur][T[cur]] -= minim;
                //cout<<"PLM!\n";
            }
            maxflow += minim;
        }
    }
    out<<maxflow<<"\n";
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(flow[i][j + N])
                out<<i<<" "<<j<<"\n";

    return 0;
}