Cod sursa(job #1558534)

Utilizator geniucosOncescu Costin geniucos Data 29 decembrie 2015 12:52:56
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

int N;

class graph
{
public:
    int N, S, D;
    void add_edge (int x, int y, int c)
    {
        X[++M] = x, Y[M] = y, C[M] = c, v[x].push_back (M);
        X[++M] = y, Y[M] = x, C[M] = 0, v[y].push_back (M);
    }

    int max_flow ()
    {
        int ans = 0;
        while (bfs ())
        {
            for (vector < int > :: iterator it = v[D].begin (); it != v[D].end (); it ++)
            if (t[Y[*it]] != -1 && F[opus (*it)] < C[opus (*it)])
            {
                int mini = 1 << 25;
                t[D] = opus (*it);
                for (int i=D; i != S; i = X[t[i]])
                    if (C[t[i]] - F[t[i]] < mini)
                        mini = C[t[i]] - F[t[i]];
                ans += mini;
                for (int i=D; i != S; i = X[t[i]])
                    F[t[i]] += mini, F[opus (t[i])] -= mini;
            }
        }
        return ans;
    }

    vector < pair < int , int > > get_paths ()
    {
        vector < pair < int , int > > ans;
        for (int i=1; i<=M; i++)
            if (F[i] > 0 && X[i] != S && X[i] != D && Y[i] != S && Y[i] != D) ans.push_back (make_pair (X[i], Y[i]));
        return ans;
    }
private:
    int M = 0, t[40009], X[40009], Y[40009], C[40009], F[40009];
    vector < int > v[1509];

    int opus (int M)
    {
        if (M & 1) return M + 1;
        return M - 1;
    }

    bool bfs ()
    {
        queue < int > cc;
        for (int i=1; i<=N; i++)
            t[i] = -1;
        cc.push (S), t[S] = 0;
        while (!cc.empty ())
        {
            int nod = cc.front ();
            cc.pop ();
            for (vector < int > :: iterator it = v[nod].begin (); it != v[nod].end (); it ++)
                if (t[Y[*it]] == -1 && C[*it] > F[*it])
                {
                    cc.push (Y[*it]), t[Y[*it]] = *it;
                    if (Y[*it] == D) return 1;
                }
        }
        return 0;
    }
}net;

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

scanf ("%d", &N), net.N = N * 2 + 2, net.S = 1, net.D = net.N;
for (int i=1; i<=N; i++)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    net.add_edge (net.S, i * 2, x);
    net.add_edge (i * 2 + 1, net.D, y);
}

for (int i=1; i<=N; i++)
    for (int j=1; j<=N; j++)
        if (i != j) net.add_edge (2 * i, 2 * j + 1, 1);

printf ("%d\n", net.max_flow ());
vector < pair < int , int > > ans = net.get_paths ();
for (vector < pair < int , int > > :: iterator it = ans.begin (); it != ans.end (); it ++)
    printf ("%d %d\n", it->first >> 1, it->second >> 1);

return 0;
}