Cod sursa(job #1513913)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 30 octombrie 2015 11:03:34
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
#include <bitset>

#define DIM 256
using namespace std;

int nrNodes, nrEdges, inside, outside;

vector <int> Edges[DIM]; int Father[DIM];
bitset <DIM> Marked; deque <int> Queue;
int Quantity[DIM][DIM], maxFlow[DIM][DIM];

bool BFS (int startNode, int finishNode)
{
    Marked.reset();
    Queue.clear();

    int ok = 0;
    Queue.push_back(startNode);
    Marked[startNode] = 1;
    Father[0] = -1;

    while (!Queue.empty())
    {
        int node = Queue.front();

        vector <int> :: iterator it;
        for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
        {
            int nextNode = *it;

            if (!Marked[nextNode] && maxFlow[node][nextNode] < Quantity[node][nextNode])
            {
                Marked[nextNode] = 1;
                Father[nextNode] = node;
                Queue.push_back(nextNode);

                if (nextNode == finishNode)
                    ok = 1;
            }
        }

        Queue.pop_front();
    }

    return ok;
}

int main ()
{
    freopen ("harta.in" ,"r", stdin );
    freopen ("harta.out","w", stdout);

    scanf ("%d", &nrNodes);
    int startNode = 0;
    int finishNode = 2 * nrNodes + 1;

    for (int i = 1; i <= nrNodes; i ++)
    {
        scanf ("%d %d", &outside, &inside);

        Edges[startNode].push_back(i);
        Edges[i].push_back(startNode);
        Edges[nrNodes + i].push_back(finishNode);
        Edges[finishNode].push_back(nrNodes + i);

        Quantity[startNode][i] = outside;
        Quantity[nrNodes + i][finishNode] = inside;

        for (int j = nrNodes + 1; j <= 2 * nrNodes; j ++)
        {
            if (j == nrNodes + i) continue;

            Edges[i].push_back(j);
            Edges[j].push_back(i);
            Quantity[i][j] = 1;
        }
    }

    int sum = 0;
    while ( BFS(startNode, finishNode) )
    {
        int node = finishNode;

        vector <int> :: iterator it;
        for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
        {
            int nextNode = *it;

            if (Marked[nextNode] && maxFlow[nextNode][node] < Quantity[nextNode][node])
            {
                int minim = Quantity[nextNode][node] - maxFlow[nextNode][node], newNode;

                newNode = nextNode;
                while (Father[newNode] != -1)
                {
                    minim = min(minim, Quantity[Father[newNode]][newNode] - maxFlow[Father[newNode]][newNode]);
                    newNode = Father[newNode];
                }

                sum += minim;
                maxFlow[nextNode][node] += minim;
                maxFlow[node][nextNode] -= minim;

                newNode = nextNode;
                while (Father[newNode] != -1)
                {
                    maxFlow[Father[newNode]][newNode] += minim;
                    maxFlow[newNode][Father[newNode]] -= minim;
                    newNode = Father[newNode];
                }
            }
        }
    }

    int nrNewEdges = 0;
    for (int i = 1; i <= nrNodes; i ++)
        for (int j = nrNodes + 1; j <= nrNodes * 2; j ++)
            if (maxFlow[i][j] == 1) nrNewEdges ++;

    printf ("%d\n", nrNewEdges);
    for (int i = 1; i <= nrNodes; i ++)
        for (int j = nrNodes + 1; j <= nrNodes * 2; j ++)
            if (maxFlow[i][j] == 1)
                printf ("%d %d\n", i, j - nrNodes);

    fclose (stdin );
    fclose (stdout);

    return 0;
}