Pagini recente » Cod sursa (job #1026052) | Cod sursa (job #1894230) | Cod sursa (job #1650707) | Cod sursa (job #462671) | Cod sursa (job #2835189)
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, s, d, max_flux;
int cap[205][205], flux[205][205], p[205];
vector <int> G[205];
vector <pair <int, int>> ans;
bool traseu[205];
bool bfs()
{
memset(traseu, 0, sizeof traseu);
queue <int> q;
q.push(s);
while(!q.empty())
{
int poz = q.front();
q.pop();
if(poz == d)
continue;
for(auto vecin : G[poz])
{
if(!traseu[vecin] && cap[poz][vecin] > flux[poz][vecin])
{
traseu[vecin] = 1;
p[vecin] = poz;
q.push(vecin);
}
}
}
return traseu[d];
}
int main()
{
fin >> n;
s = 0;
d = 2 * n + 1;
for(int i = 1; i <= n; i++)
{
int a, b;
fin >> a >> b;
cap[s][i] = a;
cap[n + i][d] = b;
}
for(int i = 1; i <= n; i++)
{
G[s].push_back(i);
G[i].push_back(s);
G[d].push_back(n + i);
G[n + i].push_back(d);
for(int j = 1; j <= n; j++)
{
if(j != i)
{
G[i].push_back(j + n);
G[j + n].push_back(i);
cap[i][j + n] = 1;
}
}
}
while(bfs())
{
for(int x = d; x != s; x = p[x])
{
flux[p[x]][x]++;
flux[x][p[x]]--;
}
max_flux++;
}
fout << max_flux << '\n';
for(int i = 1; i <= n; i++)
for(int j = n + 1; j <= 2 * n; j++)
if(flux[i][j])
fout << i << ' ' << j - n << '\n';
return 0;
}