Cod sursa(job #926123)

Utilizator vlad.maneaVlad Manea vlad.manea Data 24 martie 2013 23:01:05
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
 
#define NMAX 256
#define INFILE "harta.in"
#define OUTFILE "harta.out"
int ans, N;
 
vector<int> list[NMAX];
int capacities[NMAX][NMAX];
int flows[NMAX][NMAX];
 
void read()
{
    int x, y;
    ifstream fin(INFILE);
    fin >> N;
     
    for (int i = 1; i <= N; ++i)
    {
        fin >> x >> y;
		
		capacities[2 * N + 1][i] = x;
		capacities[i + N][2 * N + 2] = y;
		
		list[2 * N + 1].push_back(i);
		list[i].push_back(2 * N + 1);

		list[2 * N + 2].push_back(i + N);
		list[i + N].push_back(2 * N + 2);
    }

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			if (i != j)
			{
				capacities[i][j + N] = 1;
				list[i].push_back(j + N);
				list[j + N].push_back(i);
			}
		}
	}
 
    fin.close();
}
 
int traverse()
{
    int ans = 0;
    bool seen[NMAX];
    int papa[NMAX];
 
    int x, y, f, c, m;
    queue<int> nodes;
 
    for (int i = 1; i <= 2 * N + 2; ++i)
    {
        papa[i] = 0;
        seen[i] = false;
    }
 
    nodes.push(2 * N + 1);
    seen[2 * N + 1] = true;
     
    while (!nodes.empty())
    {
        x = nodes.front();
 
        for (int i = 0; i < list[x].size(); ++i) 
        {
            y = list[x][i];
 
            if (seen[y] == true || y == 2 * N + 2)
            {
                continue;
            }
 
            f = flows[x][y];
            c = capacities[x][y];
 
            if (f < c)
            {
                seen[y] = true;
                papa[y] = x;
                nodes.push(y);
            }
        }
 
        nodes.pop();
    }
 
    for (int i = 0; i < list[2 * N + 2].size(); ++i)
    {
        x = list[2 * N + 2][i];
        f = flows[x][2 * N + 2];
        c = capacities[x][2 * N + 2];
 
        if (seen[x] == true && f < c)
        {
            m = numeric_limits<int>::max();
 
            for (y = 2 * N + 2; x && m > 0; y = x, x = papa[x])
            {
                m = min(m, capacities[x][y] - flows[x][y]);
            }
 
            if (m <= 0)
            {
                continue;
            }
 
            for (y = 2 * N + 2, x = list[2 * N + 2][i]; x; y = x, x = papa[x])
            {
                flows[x][y] += m;
                flows[y][x] -= m;
            }
 
            ans += m;
        }
    }
 
    return ans;
}
 
void solve()
{
    int f;
 
    do
    {
        f = traverse();
        ans += f;
    }
    while (f);
}
 
void write()
{
    ofstream fout(OUTFILE);
    fout << ans << '\n';

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			if (flows[i][N + j] > 0)
			{
				fout << i << ' ' << j << '\n';
			}
		}
	}

    fout.close();
}
 
int main()
{
    read();
    solve();
    write();
}