Pagini recente » Cod sursa (job #1678583) | Cod sursa (job #1223113) | Cod sursa (job #860015) | Cod sursa (job #612907) | Cod sursa (job #564206)
Cod sursa(job #564206)
#include <fstream>
#include <queue>
#include <vector>
#define DIM 1001
using namespace std;
int n, m;
int c[DIM][DIM], f[DIM][DIM];
int ge[DIM], gi[DIM];
int S, D;
vector<int> t;
vector<pair<int,int> > sol;
void Read();
void EK();
void Augment();
bool BF();
void Write();
void Build();
int main()
{
Read();
Build();
EK();
Write();
return 0;
}
void Read()
{
ifstream fin("harta.in");
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> ge[i] >> gi[i];
fin.close();
}
void Build()
{
S = 0; D = 2 * n + 1;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
if (i != j) c[i][j+n] = 1;
c[S][i] = ge[i];
c[i+n][D] = gi[i];
}
}
void EK()
{
while (BF())
Augment();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j && f[i][j+n])
{
sol.push_back(make_pair(i,j));
m++;
}
}
bool BF()
{
queue<int> Q;
vector<bool> s(D+1);
t.clear(); t.resize(D+1);
s[S] = 1;
Q.push(S);
while (!Q.empty())
{
int i = Q.front();
Q.pop();
for (int j = S; j <= D; ++j)
{
if (s[j]) continue;
if (f[i][j] < c[i][j])
{
s[j] = true;
t[j] = i;
Q.push(j);
if (j == D) return true;
}
}
}
return false;
}
void Augment()
{
int i, j;
j = D;
while (j != S)
{
i = t[j];
f[i][j]++;
f[j][i]--;
j = i;
}
}
void Write()
{
ofstream fout("harta.out");
fout << m << '\n';
for (int i = 0; i < m; ++i)
fout << sol[i].first << ' ' << sol[i].second << '\n';
fout.close();
}