Pagini recente » Cod sursa (job #2687697) | Cod sursa (job #1365799) | Cod sursa (job #1205005) | Cod sursa (job #1812237) | Cod sursa (job #1538140)
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define INF 0x3f3f3f3f
using namespace std;
ifstream is("harta.in");
ofstream os("harta.out");
using VI = vector<int>;
using VVI = vector<VI>;
int n, m;
VI in, out, t;
VVI g, c;
bitset<205> ok;
void Read();
void Build();
bool Bfs();
int main()
{
Read();
Build();
t = VI(2 * n + 2);
int fmin, answ = 0;
while ( Bfs() && answ < m )
for ( int nodv = n + 1; nodv <= 2 * n; ++nodv )
{
if ( !ok[nodv] || c[nodv][2 * n + 1] < 0 )
continue;
fmin = INF;
t[2 * n + 1] = nodv;
for ( int x = 2 * n + 1; x; x = t[x] )
fmin = min(fmin, c[t[x]][x]);
if ( !fmin )
continue;
for ( int x = 2 * n + 1; x; x = t[x] )
{
--c[t[x]][x];
++c[x][t[x]];
}
++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 << j << " " << i << "\n";
--m;
}
is.close();
os.close();
return 0;
}
bool Bfs()
{
ok.reset();
queue<int> q;
q.push(0);
int nod;
while ( !q.empty() )
{
nod = q.front();
q.pop();
if ( nod == n + 1 )
continue;
for ( const auto &nodv : g[nod] )
if ( !ok[nodv] && c[nod][nodv] > 0 )
{
ok[nodv] = 1;
q.push(nodv);
t[nodv] = nod;
}
}
return ok[n + 1];
}
void Build()
{
g = VVI(2 * n + 2);
c = VVI(2 * n + 2, VI(2 * n + 2));
for ( int i = 1; i <= n; ++i )
{
g[0].push_back(i);
g[n + i].push_back(2 * n + 1);
c[0][i] = in[i];
c[n + i][2 * n + 1] = out[i];
}
for ( int i = 1; i < n; ++i )
for ( int j = i + 1; j <= n; ++j )
{
c[i][n + j] = 1;
g[i].push_back(n + j);
g[n + j].push_back(i);
c[j][n + i] = 1;
g[j].push_back(n + i);
g[n + i].push_back(j);
}
}
void Read()
{
is >> n;
in = out = VI(n + 1);
for ( int i = 1; i <= n; ++i )
{
is >> in[i] >> out[i];
m += in[i];
}
}