Cod sursa(job #1444515)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 29 mai 2015 20:46:14
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.27 kb
#include <fstream>
#include <cstring>
#include <vector>

#define vint vector<int>::iterator

using namespace std;

ifstream fin ("harta.in");
ofstream fout ("harta.out");

int n,m,x,y;
int C[301][301],F[301][301],viz[301],q[301],T[301];
vector<int> G[301];

struct edge
{
    int x,y;
}e[90001];

bool bfs (int x)
{
    memset (viz,0,sizeof(viz));
    viz[x] = 1;
    int l = 1;
    q[l] = x;

    for (int s=1; s<=l; ++s)
    {
        x = q[s];
        for (vint it = G[x].begin (); it != G[x].end (); ++it)
        {
            if (!viz[*it] && C[x][*it] != F[x][*it])
            {
                viz[*it] = 1;
                q[++l] = *it;
                T[*it] = x;
            }
        }
    }

    return viz[n];
}

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
    {
        fin>>x>>y;

        C[0][i] = x;
        C[i+n][2*n+1] = y;

        G[0].push_back (i);
        G[i].push_back (0);
        G[i+n].push_back (2*n+1);
        G[2*n+1].push_back (i+n);

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

    int nn = n;
    n = 2*n+1;

    while (bfs (0))
    {
        for (vint it = G[n].begin (); it != G[n].end(); ++it)
        {
            if (!viz[*it] || C[*it][n] == F[*it][n])
                continue;

            int minf = C[*it][n] - F[*it][n];

            for (int i = *it; i != 0; i = T[i])
            {
                minf = min (minf,C[T[i]][i] - F[T[i]][i]);
            }

            F[*it][n] += minf;
            F[n][*it] -= minf;

            for (int i = *it; i != 0; i = T[i])
            {
                F[T[i]][i] += minf;
                F[i][T[i]] -= minf;
            }
        }
    }

    for (int i=1; i<=nn; ++i)
    {
        for (vint it = G[i].begin (); it != G[i].end(); ++it)
        {
            if (F[i][*it] && *it != 0)
            {
                ++m;
                e[m].x = i;
                e[m].y = *it - nn;
            }
        }
    }

    fout<<m<<"\n";

    for (int i=1; i<=m; ++i)
    {
        fout<<e[i].x<<" "<<e[i].y<<"\n";
    }
}