Pagini recente » Cod sursa (job #1145137) | Cod sursa (job #135500) | Cod sursa (job #3226943) | Cod sursa (job #365744) | Cod sursa (job #2956619)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int maxn = 305;
int intrare[maxn];
int iesire[maxn];
int dist[maxn];
struct muchie {
int nod, vec, flux, cap;
};
vector <muchie> v[maxn]; /// graful generat sa bag flux pe el
muchie tata[maxn];
queue <int> q;
vector <muchie> drum;
int n;
int sursa, destinatie;
bool bfs()
{
for(int i = 1; i <= n * 2 + 2; i++)
{
dist[i] = (1 << 30);
tata[i] = {0, 0, 0};
}
dist[sursa] = 0;
q.push(sursa);
while(!q.empty())
{
int nod = q.front();
q.pop();
for(auto it : v[nod])
{
if(dist[it.vec] > dist[nod] + 1 && it.flux < it.cap) /// pot trimite flux pe aici
{
dist[it.vec] = dist[nod] + 1;
tata[it.vec] = it;
q.push(it.vec);
}
}
}
if(dist[destinatie] != (1 << 30))
return 1;
return 0;
}
int main()
{
in >> n;
/// pun 1...n nodurile de pe partea stanga
/// pun n+1, n+2, ..., 2n nodurile de pe partea dreapta
/// 2n+1 - sursa, 2n+2 - destinatie
sursa = 2 * n + 1;
destinatie = 2 * n + 2;
int sol = 0;
for(int i = 1; i <= n; i++)
{
in >> iesire[i] >> intrare[i];
/// trag liniile 0->i, (n+i) -> 2n+1
v[sursa].push_back({sursa, i, 0, iesire[i]});
v[i].push_back({i, sursa, 0, 0});
v[n + i].push_back({n + i, destinatie, 0, intrare[i]});
v[destinatie].push_back({destinatie, n + i, 0, 0});
sol = sol + iesire[i];
}
for(int i = 1; i <= n; i++)
{
for(int j = n + 1; j <= 2 * n; j++)
{
if(i + n != j) /// trag muchiile (x, y) de capacitate 1 unde x, y nu reprezita acelasi lucru
{
v[i].push_back({i, j, 0, 1});
v[j].push_back({j, i, 0, 0});
}
}
}
/*
for(int i = 1; i <= 2 * n + 2; i++)
for(auto it : v[i])
cerr << i << " " << it.vec << " " << it.cap << "\n";
*/
/// acum dau copy paste la flux
while(bfs()) /// cat timp gasesc un drum de la 1 la n
{
int act = destinatie;
drum.clear();
while(tata[act].nod != 0)
{
drum.push_back(tata[act]);
act = tata[act].nod;
}
int posibil = (1 << 30); /// fluxul maxim pe care il pot trimite pe drumul gasit
for(auto it : drum) /// calculez ce flux pot trimite
posibil = min(posibil, it.cap - it.flux);
for(auto m : drum) /// scad si adun fluxul pe care il bag din toate muchiile
{
int x = m.nod;
int y = m.vec;
for(int i = 0; i < v[x].size(); i++) /// gasesc muchia (x, y) si adun fluxul bagat
{
if(v[x][i].vec == y)
{
v[x][i].flux += posibil;
break;
}
}
for(int i = 0; i < v[y].size(); i++)
{
if(v[y][i].vec == x)
{
v[y][i].flux -= posibil; /// gasesc muchia (y, x) si scad fluxul bagat
break;
}
}
}
}
out << sol << "\n";
for(int i = 1; i <= n; i++)
for(auto it : v[i])
if(it.flux > 0)
out << it.nod << " " << it.vec - n << "\n";
return 0;
}