Pagini recente » Cod sursa (job #2128650) | Cod sursa (job #2499475) | Cod sursa (job #1294254) | Cod sursa (job #2064720) | Cod sursa (job #891924)
Cod sursa(job #891924)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream in ("harta.in");
ofstream out ("harta.out");
const int MAXN = 210;
int N, S, D;
vector <int> Graf[MAXN];
int C[MAXN][MAXN], F[MAXN][MAXN];
int T[MAXN];
bool Viz[MAXN];
inline bool BFS ()
{
queue <int> Q;
vector <int> :: iterator it;
int nod;
for (nod = 0; nod <= D; nod ++){
T[nod] = 0;
Viz[nod] = 0;
}
Q.push (S);
Viz[S] = 1;
T[S] = -1;
while (!Q.empty ()){
nod = Q.front ();
Q.pop ();
if (nod == D)
continue;
for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it)
if (!Viz[*it] && C[nod][*it] != F[nod][*it]){
Q.push (*it);
T[*it] = nod;
Viz[*it] = 1;
}
}
return T[D];
}
void Augment ()
{
int nod, fmin;
bool ok = 1;
vector <int> :: iterator it;
for ( ; BFS (); )
for (it = Graf[D].begin (); it != Graf[D].end (); ++ it){
ok = 1;
if (!Viz[*it] || C[*it][D] == F[*it][D])
continue;
T[D] = *it;
for (nod = D; nod != S; nod = T[nod])
if (C[ T[nod] ][nod] == F[ T[nod] ][nod])
ok = 0;
if (!ok)
continue;
for (nod = D; nod != S; nod = T[nod]){
F[ T[nod] ][nod] ++;
F[nod][ T[nod] ] --;
}
}
}
int main()
{
int M, i, j, a, b;
int Ans = 0;
in >> N;
S = 0;
D = 2 * N + 1;
for (i = 1; i <= N; i ++){
in >> a >> b;
Ans += a;
Graf[S].push_back (i);
Graf[i].push_back (S);
Graf[D].push_back (i + N);
Graf[i + N].push_back (D);
C[S][i] = a;
C[i + N][D] = b;
for (j = N + 1; j <= 2 * N; j ++)
if (i != j - N){
Graf[i].push_back (j);
Graf[j].push_back (i);
C[i][j] = 1;
}
}
Augment ();
cout << Ans << "\n";
for (i = 1; i <= N; i ++)
for (j = N + 1; j <= 2 * N; j ++)
if (F[i][j] == 1)
cout << i << " " << j - N << "\n";
return 0;
}