Pagini recente » Monitorul de evaluare | Cod sursa (job #2869683) | Cod sursa (job #1333270) | Cod sursa (job #2832346) | Cod sursa (job #1223311)
#include <cstring>
#include <fstream>
#include <queue>
using namespace std;
const int MAXN = 103;
int N, S, D, cf[2*MAXN][2*MAXN], tata[2*MAXN];
void read()
{
ifstream fin("harta.in");
fin >> N;
S = 0;
D = 2*N + 1;
for (int i = 1; i <= N; ++i)
fin >> cf[S][i] >> cf[i+N][D];
fin.close();
}
inline void relax(int x, int y, int c)
{
cf[x][y] -= c;
cf[y][x] += c;
}
bool BFS(int S, int D)
{
memset(tata, -1, sizeof tata);
queue < int > Q;
Q.push(S);
while ( !Q.empty() )
{
int x = Q.front();
Q.pop();
for (int i = 1; i <= D; ++i)
if ( cf[x][i] && tata[i] == -1 )
{
Q.push(i);
tata[i] = x;
}
}
return tata[D] != -1;
}
int fluxMax()
{
int flux = 0;
while ( BFS(S, D) )
for (int i = N + 1; i <= 2*N; ++i)
if ( cf[i][D] && tata[i] != -1 )
{
int f = cf[i][D];
for (int j = i ; j != S; j = tata[j] )
f = min(f, cf[ tata[j] ][j]);
relax(i, D, f);
for (int j = i; j != S; j = tata[j] )
relax(tata[j], j, f);
flux += f;
}
return flux;
}
int main()
{
read();
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
cf[i][j+N] = (i != j);
ofstream fout("harta.out");
fout << fluxMax() << '\n';
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
if ( i != j && !cf[i][j+N] )
fout << i << ' ' << j << '\n';
fout.close();
return 0;
}