Cod sursa(job #1444411)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 29 mai 2015 19:05:01
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 3.49 kb
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#include <string>
using namespace std;

const int maxN = 100 + 100 + 2;

bool BFS(int src, int N, vector<int> adjList[],
         int flow[][maxN], int capacity[][maxN], int parent[], bool visited[]);

int main()
{
    int N, i, x, y, j;
    ifstream f("harta.in");
    f >> N;
    int outer[N + 1], inner[N + 1], sumInner = 0, sumOuter = 0;
    for (i = 1; i <= N; i++)
    {
        f >> x >> y;
        outer[i] = x;
        inner[i] = y;
        sumOuter += x;
        sumInner += y;
    }
    f.close();

    vector<int> adjList[maxN];
    int flow[maxN][maxN], capacity[maxN][maxN], parent[maxN];
    bool visited[maxN];
    for (i = 0; i <= N + N + 1; i++)
    {
        fill(flow[i], flow[i] + maxN, 0);
        fill(capacity[i], capacity[i] + maxN, 0);
    }

    for (i = 1; i <= N; i++)
    {
        adjList[0].push_back(i);
        adjList[i].push_back(0);
        capacity[0][i] = inner[i];
    }

    for (i = N + 1; i <= N + N ; i++)
    {
        adjList[N + N + 1].push_back(i);
        adjList[i].push_back(N + N + 1);
        capacity[i][N + N + 1] = outer[i - N];
    }

    //!
    for(i = 1; i <= N; i++)
        for(j = i + 1; j <= N; j++)
        {
            adjList[i].push_back(j + N);
            adjList[j + N].push_back(i);
            capacity[i][j + N] = 1;
            adjList[j].push_back(i + N);
            adjList[i + N].push_back(j);
            capacity[j][i + N] = 1;
        }


    int minFlow, result = 0;
    int currentNode;
    while (BFS(0, N + N + 1, adjList, flow, capacity, parent, visited))
    {
        for (j = 0; j < adjList[N + N + 1].size(); j++)
        {
            currentNode = adjList[N + N + 1][j];
            if (flow[currentNode][N + N + 1] != capacity[currentNode][N + N + 1] && visited[currentNode])
            {
                minFlow = INT_MAX;
                parent[N + N + 1] = currentNode;
                for (i = N + N + 1; parent[i] != -1; i = parent[i])
                    minFlow = min(minFlow, capacity[parent[i]][i] - flow[parent[i]][i]);

                if (minFlow)
                {
                    for (i = N + N + 1; parent[i] != -1; i = parent[i])
                    {
                        flow[parent[i]][i] += minFlow;
                        flow[i][parent[i]] -= minFlow;
                    }

                    result += minFlow;
                }
            }
        }
    }

    ofstream g("harta.out");
    if (result != sumInner)
        g << "0";
    else
    {
        g << result << '\n';
        for (i = 1; i <= N; i++)
            for (j = N + 1; j <= N + N; j++)
                if (flow[i][j] == 1)
                    g << i << " " << j - N << '\n';
    }
    g.close();

    return 0;
}

bool BFS(int src, int N, vector<int> adjList[],
         int flow[][maxN], int capacity[][maxN], int parent[], bool visited[])
{
    fill(visited, visited + N + 1, false);

    queue<int> q;
    q.push(src);
    visited[src] = true;
    parent[src] = -1;

    int x, i;
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        if (x != N)
        {
            for (i = 0; i < adjList[x].size(); i++)
            {
                int neighbor = adjList[x][i];
                if (capacity[x][neighbor] != flow[x][neighbor] && !visited[neighbor])
                {
                    visited[neighbor] = true;
                    q.push(neighbor);
                    parent[neighbor] = x;
                }
            }
        }
    }

    return visited[N];
}