Pagini recente » Profil siliconvalleyguy | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3361087) | Cod sursa (job #3361089)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
// #include <bits/std++.h>
#define in fin
#define out fout
using namespace std;
const int NMAX = 105;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct muchie{
int x, y, pereche, f, c;
};
vector<muchie> mch;
pair<int, int> last[2 * NMAX];
bool mrc[2 * NMAX]; // 2 * NMAX pt ca am 2 layere de cate n si dupa sursie si noelle
int sursie, noelle;
// get it? sursa + susie = sursie? get it?
vector<int> g[2 * NMAX];
int n, m;
void fa_bfs_pls(){
for(int i = 1; i <= 2 * n + 2; i++){
mrc[i] = 0;
last[i] = {0, -1};
}
queue<int> q;
q.push(sursie);
mrc[sursie] = 1;
while(!q.empty()){
int x = q.front(); q.pop();
for(const int &cine : g[x]){
int y = mch[cine].y;
if(!mrc[y] && mch[cine].f < mch[cine].c){
mrc[y] = 1;
q.push(y);
last[y] = {x, cine};
}
}
}
}
int gaseste_minimul_pls(int nod, int minim_ude){
while(last[nod].second != -1){
minim_ude = min(minim_ude, mch[ last[nod].second ].c - mch[ last[nod].second ].f);
nod = last[nod].first;
}
return minim_ude;
}
void satureaza_pls(int nod, int val){
while(last[nod].second != -1){
int id = last[nod].second; // i ain't writing allat de fiecare data
mch[id].f += val;
mch[ mch[id].pereche ].f -= val;
nod = last[nod].first;
}
}
signed main(){
ios_base::sync_with_stdio(false);
in.tie(NULL);
in >> n;
// primii 1...n --> nodurile ca sa determin outurile
// dupaia n + 1...2 * n --> nodurile ca sa determin inurile (ma rog asta ramane)
// sursie = 2 * n + 1
// noelle = 2 * n + 2
sursie = 2 * n + 1;
noelle = 2 * n + 2;
for(int i = 1; i <= n; i++){
for(int j = n + 1; j <= 2 * n; j++){
if(i == j - n) continue;
int id = mch.size(), idp = mch.size() + 1;
mch.push_back({ i, j, idp, 0, 1 });
mch.push_back({ j, i, id, 0, 0 });
g[i].push_back(id);
g[j].push_back(idp);
}
}
vector< pair<int, int> > ralsei; // vecinii lui noelle
// stiu ca sunt de la n + 1 la 2 * n DAR vreau si indexii in mch usor
for(int i = 1; i <= n; i++){ // yet again, aceeasi indexare malefica
int intra, iese; in >> iese >> intra; // pot sa intru eu in rals- cine a spus aia
// bro lowk strid e un band destul de fain da au doar 5000 de monthly listeners TwT
// gen ascultam in general doar sommar de la ei si credeam ca is band destul de popular ca imi place melodia
// dar nu
// i js put on albumul descent (cel cu sommar)
// idk daca le pot zice dsbm da macar ceva influente is (ca bro se plange in melodii)
int id = mch.size(), idp = mch.size() + 1;
mch.push_back( {sursie, i, idp, 0, iese} );
mch.push_back( {i, sursie, id, 0, 0} );
g[sursie].push_back(id);
g[i].push_back(idp);
id = mch.size(), idp = mch.size() + 1;
mch.push_back( {i + n, noelle, idp, 0, intra} );
mch.push_back( {noelle, i + n, id, 0, 0} );
g[i + n].push_back(id);
g[noelle].push_back(idp);
ralsei.push_back({i + n, id});
}
int total = 0;
while(true){
fa_bfs_pls(); // multu
if(!mrc[noelle]) break;
// cerr << "am ajuns!\n";
for(const pair<int, int> &cine : ralsei){
int y = cine.first;
int id = cine.second;
if(!mrc[y]) continue;
if(mch[id].f == mch[id].c) continue;
// cerr << "--> incerc cu y = " << y << '\n';
int add = gaseste_minimul_pls(y, mch[id].c - mch[id].f);
// cerr << "--> init = " << mch[id].c - mch[id].f << '\n';
// cerr << "--> add = " << add << '\n';
if(add == 0) continue;
satureaza_pls(y, add);
mch[id].f += add;
mch[ mch[id].pereche ].f -= add;
total += add;
}
}
out << total << '\n';
for(const muchie &x : mch){
if(1 <= x.x && x.x <= n && n < x.y && x.y <= 2 * n && x.f == 1){
out << x.x << " " << x.y - n << '\n';
}
}
return 0;
}