Pagini recente » Cod sursa (job #1227156) | Cod sursa (job #172773) | Cod sursa (job #2609573) | Cod sursa (job #645582) | Cod sursa (job #2662081)
#define fisier "harta"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
const int S = 100, N = 2*S + 2, INF = 110000;
int C[N][N], T[N], n, s;
#include <vector>
std::vector<int> L[N];
#include <deque>
#include <bitset>
std::bitset<N> E;
bool bfs()
{
E = 1;
for (std::deque<int> D = {0}; D.size(); D.pop_front())
for (int back: L[D.front()])
if (not E[back] and C[D.front()][back])
{
D.push_back(back);
E[back] = true;
T[back] = D.front();
if (back == n)
return true;
}
return false;
}
int main()
{
in >> s;
n = 2*s + 1;
for (int i = 1; i <= s; i++)
for (int j = 1; j <= s; j++)
if (i != j)
{
C[i][s+j] = 1;
L[i].push_back(s+j);
L[s+j].push_back(i);
}
for (int i = 1; i <= s; i++)
{
int degIn, degOut;
in >> degOut >> degIn;
C[0][i] = degOut;
C[s+i][n] = degIn;
L->push_back(i);
L[s+i].push_back(n);
L[n].push_back(s+i);
}
int m = 0;
while (bfs())
for (int t: L[n])
if (E[t] and C[t][n])
{
T[n] = t;
int min = INF;
for (int i = t; i; i = T[i])
min = std::min(min, C[ T[i] ][i]);
m += min;
for (int i = n; i; i = T[i])
{
C[ T[i] ][i] -= min;
C[i][ T[i] ] += min;
}
}
out << m << '\n';
for (int i = 1; i <= s; i++)
for (int j = 1; j <= s; j++)
if (i != j and not C[i][s+j])
out << i << ' ' << j << '\n';
}