Pagini recente » Cod sursa (job #488404) | Cod sursa (job #1719068) | Cod sursa (job #2340315) | Cod sursa (job #2552346) | Cod sursa (job #2603464)
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, in, out, i, j, c[205][205], f[205][205], tata[205];
bool viz[205];
struct muchie{
int x, y;
};
vector <int> g[105];
vector <muchie> sol;
queue <int> q;
void que(){
memset(viz, 0, sizeof(viz));
viz[0] = 1, q.push(0);
while(!q.empty()){
int nod = q.front();
q.pop();
for(int i = 0; i < g[nod].size(); i++){
int nou = g[nod][i];
if(!viz[nou] && f[nod][nou] < c[nod][nou])
viz[nou] = 1, tata[nou] = nod, q.push(nou);
}
}
}
int mi(int nod){
int Min = c[nod][2*n+1] - f[nod][2*n+1];
while(nod){
int nou = tata[nod];
Min = min(Min, c[nou][nod] - f[nou][nod]);
nod = nou;
}
return Min;
}
void back(){
for(int i = 0; i < g[2*n+1].size(); i++){
int nod = g[2*n+1][i];
if(viz[nod]){
int Min = mi(nod);
if(!Min)
continue;
f[nod][2*n+1] += Min;
f[2*n+1][nod] -= Min;
while(nod){
int nou = tata[nod];
f[nou][nod] += Min;
f[nod][nou] -= Min;
nod = nou;
}
}
}
}
int main()
{
fin >> n;
for(i = 1; i <= n; i++){
fin >> in >> out;
if(in){
g[0].push_back(i), g[i].push_back(0);
c[0][i] = in;
for(j = 1; j <= n; j++)
if(i != j)
g[i].push_back(n+j), g[n+j].push_back(i),
c[i][n+j] = 1;
}
if(out)
g[i+n].push_back(2*n+1), g[2*n+1].push_back(i+n),
c[i+n][2*n+1] = out;
}
while(!viz[2*n+1]){
que();
if(viz[2*n+1])
back();
viz[2*n+1] = !viz[2*n+1];
}
for(i = 1; i <= n; i++)
for(j = n+1; j <= 2*n; j++)
if(f[i][j])
sol.push_back({i,j-n});
fout << sol.size() << '\n';
for(i = 0; i < sol.size(); i++)
fout << sol[i].x << ' ' << sol[i].y << '\n';
return 0;
}