Pagini recente » Cod sursa (job #2434285) | Cod sursa (job #2381652) | Cod sursa (job #2811770) | Cod sursa (job #2254535) | Cod sursa (job #1385837)
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
ifstream is("harta.in");
ofstream os("harta2.out");
int N, n, m;
vector<bool> ok;
vector<int> in, out, t;
vector<vector<int> > c, g, wr;
void Read();
void Build();
bool BFS();
int main()
{
Read();
Build();
t = vector<int>(N + 1);
wr = vector<vector<int> >(n + 1, vector<int>(n + 1, 0));
int answ = 0, fmin;
while ( BFS() && answ < m )
for ( int nodv = n + 1; nodv < N; ++nodv )
if ( ok[nodv] && c[nodv][N] > 0 )
{
t[N] = nodv;
// if ( wr[t[t[N]]][t[N] - n] )
// continue;
fmin = INF;
for ( int i = N; i; i = t[i] )
fmin = min(fmin, c[t[i]][i]);
if ( !fmin )
continue;
wr[t[t[N]]][t[N] - n] = 1;
for ( int i = N; i; i = t[i] )
{
--c[t[i]][i];
++c[i][t[i]];
}
++answ;
}
os << m << "\n";
for ( int i = 1; i <= n && m; ++i )
for ( int j = 1; j <= n && m; ++j )
if ( c[i + n][j] )
{
os << i << " " << j << "\n";
// --m;
}
is.close();
os.close();
return 0;
}
bool BFS()
{
ok = vector<bool>(N + 1, 0);
queue<int> q;
q.push(0);
ok[0] = 1;
int nod;
while ( !q.empty() )
{
nod = q.front();
q.pop();
if ( nod == N )
continue;
for ( vector<int>::iterator nodv = g[nod].begin(); nodv != g[nod].end(); ++nodv )
if ( !ok[*nodv] && c[nod][*nodv] > 0 )
{
ok[*nodv] = 1;
t[*nodv] = nod;
q.push(*nodv);
}
}
return ok[N];
}
void Build()
{
N = 2 * n + 1;
c = vector<vector<int> >(N + 1, vector<int>(N + 1));
g = vector<vector<int> >(N + 1);
for ( int i = 1; i <= n; ++i )
{
c[0][i] = in[i];
c[n + i][N] = out[i];
g[n + i].push_back(N);
g[0].push_back(i);
}
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= n; ++j )
if ( i != j )
{
c[i][n + j] = 1;
g[i].push_back(n + j);
g[n + j].push_back(i);
}
}
void Read()
{
is >> n;
in = out = vector<int>(n + 1);
for ( int i = 1; i <= n; ++i )
{
is >> out[i] >> in[i];
m += out[i];
}
}