Pagini recente » Cod sursa (job #2932317) | Cod sursa (job #415405) | Cod sursa (job #1684663) | Cod sursa (job #2860564) | Cod sursa (job #2961345)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define d double
#define in int
#define si(x) scanf('%d', &x)
#define sl(x) scanf('%lld', &x)
#define ss(s) scanf('%s', s)
#define pi(x) printf('%d', x)
#define pl(x) printf('%lld', x)
#define ps(s) printf('%s', s)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
#define modulo 1000000007
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define inf INT_MAX
typedef vector<pii> vpii;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,m, x,y, fluxCurent, total;
int start, final;
vector<vector<int>>capacitate, flux;
vector<vector<int>> graf;
vector<int> vizitat, nod_flux;
void read(){
fin>>n;
start = 0;
final = 2*n + 1;
graf = vector<vector<int>>(final + 1);
capacitate = vector<vector<int>>(final + 1, vector<int>(final + 1, 0));
flux = vector<vector<int>>(final + 1, vector<int>(final + 1, 0));
for(int i=1;i<=n;i++){
fin>>x>>y;
graf[start].push_back(i);
graf[n + i].push_back(final);
capacitate[start][i] = x;
capacitate[n+i][final] = y;
for(int j=n+1;j<final;j++){
if(j!= n+i){
graf[i].push_back(j);
graf[j].push_back(i);
capacitate[i][j] = 1;
}
}
}
}
int bfs(){
vizitat = vector<int>(final + 1, 0);
queue<int> coada;
coada.push(start);
vizitat[start] = 1;
while(!coada.empty()){
int nodCurent = coada.front();
coada.pop();
for(int i=0;i<graf[nodCurent].size();i++){
if(capacitate[nodCurent][graf[nodCurent][i]] > 0 && vizitat[graf[nodCurent][i]] == 0){
nod_flux[graf[nodCurent][i]] = nodCurent;
if(graf[nodCurent][i] == final)
return 1;
coada.push(graf[nodCurent][i]);
vizitat[graf[nodCurent][i]] = 1;
}
}
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);
read();
nod_flux = vector<int>(final + 1, -1);
while(bfs()){
fluxCurent = inf;
for(int i = final;i!= start;i = nod_flux[i]){
fluxCurent = min(fluxCurent, capacitate[nod_flux[i]][i]);
}
for(int i = final;i!= start;i = nod_flux[i]){
capacitate[nod_flux[i]][i] -= fluxCurent;
capacitate[i][nod_flux[i]] += fluxCurent;
}
total += fluxCurent;
}
fout<<total<<endl;
for(int i=1;i<=n;i++){
for(int j=0;j<graf[i].size();j++){
if(capacitate[i][graf[i][j]] == 0 && graf[i][j] > n)
fout<<i<<" "<<graf[i][j] - n<<endl;
}
}
return 0;
}