Pagini recente » Cod sursa (job #2945755) | Cod sursa (job #1922029) | Cod sursa (job #2900964) | Cod sursa (job #2275139) | Cod sursa (job #1777104)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int source, destination, N, x, y, solution;
int C[256][256], F[256][256], T[256];
vector <int> L[256];
bitset <256> v;
queue <int> Q;
inline bool BFS()
{
v.reset();
Q.push(source);
while(!Q.empty())
{
int node = Q.front();
Q.pop();
for(int i = 0; i < L[node].size(); i ++)
{
int neighbour = L[node][i];
if(v[neighbour] == 0 && C[node][neighbour] > F[node][neighbour])
{
Q.push(neighbour);
v[neighbour] = 1;
T[neighbour] = node;
}
}
}
if(v[destination] == 1)
{
return true;
}
return false;
}
int main()
{
fin >> N;
source = 0;
destination = 2 * N + 1;
for(int i = 1; i <= N; i ++)
{
fin >> x >> y;
L[source].push_back(i);
L[i].push_back(source);
C[source][i] = x;
L[i + N].push_back(destination);
L[destination].push_back(i + N);
C[i + N][destination] = y;
}
for(int i = 1; i <= N; i ++)
{
for(int j = 1; j <= N; j ++)
{
if(i ^ j)
{
L[i].push_back(j + N);
L[j + N].push_back(i);
C[i][j + N] = 1;
}
}
}
while(BFS())
{
int Fmin = (1 << 30);
for(int i = 0; i < L[destination].size(); i ++)
{
int x = L[destination][i];
if(C[x][destination] > F[x][destination] && v[x] == 1)
{
while(x > source)
{
Fmin = min(Fmin, C[ T[x] ][x] - F[ T[x] ][x]);
x = T[x];
}
x = L[destination][i];
F[x][destination] += Fmin;
F[destination][x] -= Fmin;
while(x > source)
{
F[ T[x] ][x] += Fmin;
F[x][ T[x] ] -= Fmin;
x = T[x];
}
solution += Fmin;
}
}
}
fout << solution << '\n';
for(int i = 1; i <= N; i ++)
{
for(int j = 1; j <= N; j ++)
{
if(F[i][j + N] == 1)
{
fout << i << " " << j << '\n';
}
}
}
return 0;
}