Pagini recente » Cod sursa (job #694606) | Cod sursa (job #1071103) | Cod sursa (job #1930291) | Cod sursa (job #2641260) | Cod sursa (job #2594537)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 100;
int N;
int inDeg[NMAX + 2], outDeg[NMAX + 2];
int S, D;
vector <int> g[2 * NMAX + 5];
int capacity[2 * NMAX + 5][2 * NMAX + 5], flow[2 * NMAX + 5][2 * NMAX + 5];
int bef[2 * NMAX + 5];
queue <int> Q;
bool seen[2 * NMAX + 5];
bool bfs()
{
for(int i = S; i <= D; i++)
seen[i] = false;
Q.push(S);
seen[S] = true;
while(!Q.empty())
{
int node = Q.front();
Q.pop();
for(auto it : g[node])
if(!seen[it] && capacity[node][it] > flow[node][it])
{
seen[it] = true;
bef[it] = node;
Q.push(it);
}
}
return seen[D];
}
int main()
{
fin >> N;
int roads = 0;
for(int i = 1; i <= N; i++)
{
fin >> outDeg[i] >> inDeg[i];
roads += outDeg[i];
}
fout << roads << '\n';
S = 0, D = 2 * N + 1;
for(int i = 1; i <= N; i++)
{
g[S].push_back(i);
g[i].push_back(S);
capacity[S][i] = outDeg[i];
g[i + N].push_back(D);
g[D].push_back(i + N);
capacity[i + N][D] = inDeg[i];
for(int j = 1; j <= N; j++)
if(i != j)
{
g[i].push_back(j + N);
g[j + N].push_back(i);
capacity[i][j + N] = 1;
}
}
while(bfs())
{
for(auto it : g[D])
{
int pumpFlo = capacity[it][D] - flow[it][D];
for(int node = it; node != S; node = bef[node])
pumpFlo = min(pumpFlo, capacity[bef[node]][node] - flow[bef[node]][node]);
flow[it][D] += pumpFlo;
flow[D][it] -= pumpFlo;
for(int node = it; node != S; node = bef[node])
{
flow[bef[node]][node] += pumpFlo;
flow[node][bef[node]] -= pumpFlo;
}
}
}
for(int i = 1; i <= N; i++)
for(auto it : g[i])
if(flow[i][it] == 1)
fout << i << ' ' << it - N << '\n';
return 0;
}