Nu aveti permisiuni pentru a descarca fisierul grader_test10.ok

Cod sursa(job #1443919)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 29 mai 2015 01:18:40
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define NMax 310
#define MMax 5010
#define INF 2000000000

using namespace std;

int source, destination;

int ans;
int n, m;
int from[NMax];
vector <int> G[NMax];
int residual_graph[NMax][NMax];
int flow[NMax][NMax];
bool viz[NMax];

/// residual graph are la pozitia [i][j] pe x unde x este capacitatea - fluxul pe muchia i -> j
/// si are la pozitia [j][i] pe y unde y este fluxul pe i -> j daca acesta este > 0

inline int In(const int & x)
{
    return x + n;
}

inline int Out(const int & x)
{
    return x + n + n;
}

void Read()
{
    ifstream f ("harta.in");
    f >> n;
    source = 3*n + 1;
    destination = 3*n + 2;
    for (int i = 1; i <= n; ++ i)
    {
        int x, y;
        f >> x >>y;
        G[source].push_back(In(i));
        G[In(i)].push_back(source);
        residual_graph[source][In(i)] = x;

        for (int j = 1; j <= n; ++ j)
        {
            if (i != j)
            {
                G[In(i)].push_back(j);
                G[j].push_back(In(i));
                residual_graph[In(i)][j] = 1;
            }
        }
        G[Out(i)].push_back(i);
        G[i].push_back(Out(i));
        residual_graph[i][Out(i)] = y;

        G[Out(i)].push_back(destination);
        G[destination].push_back(Out(i));
        residual_graph[Out(i)][destination] = n;
    }
    f.close();

}

inline bool BFS()
{
    queue <int> Q;
    int i;
    for (i=1; i<=3*n + 2; ++i)
        from[i] = 0, viz[i] = false;
    Q.push(source);
    viz[source] = true;
    while(!Q.empty())
    {
        int node = Q.front(); Q.pop();
        for (vector<int>::iterator it = G[node].begin(); it!=G[node].end(); ++it)
            if (!viz[*it] && residual_graph[node][*it] > 0)
            {
                from[*it] = node;
                viz[*it] = true;
                Q.push(*it);
            }
    }
    return viz[destination];
}

void Solve()
{
    while (BFS()) /// cat timp mai am cai de augmentare
    {
        int i;
        for (i=Out(1); i<=Out(n); ++i)
            if (residual_graph[i][destination] > 0 && from[i])
            {
                int localflow = residual_graph[i][destination];
                int node = i;
                while (node != source)
                {
                    localflow = min(localflow, residual_graph[from[node]][node]);
                    node = from[node];
                }
                ans += localflow;
            /// poate am saturat o muchie mai inainte in arborele BFS si acum nu mai are rost sa fac vreo ceva
                if (localflow == 0)
                    continue;
                node = i;
                residual_graph[i][destination] -= localflow;
                residual_graph[destination][i] += localflow;
                flow[i][destination] += localflow;

                while (node != source)
                {
                    flow[from[node]][node] += localflow;
                    flow[node][from[node]] -= localflow;
                    residual_graph[from[node]][node] -= localflow;
                    residual_graph[node][from[node]] += localflow;
                    node = from[node];
                }
            }
    }
}

void Write()
{

    ofstream g("harta.out");
    g<<ans<<"\n";
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
        {
            if (i == j)
                continue;
            if (flow[In(i)][j] == 1)
                g << i << " " << j << "\n";
        }
    g.close();
}


int main()
{
    Read();
    Solve();
    Write();
    return 0;
}