Pagini recente » Cod sursa (job #2134011) | Cod sursa (job #582461) | Cod sursa (job #1468125) | Cod sursa (job #843030) | Cod sursa (job #2962358)
#pragma GCC optimize "O3"
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
queue<int> bfs;
vector<vector<int>> lista;
int cap[205][205];
int main(){
int n, t, x, y;
fin>>n;
t = 2 * n + 2;
lista.resize(t);
for(int i=1; i<=n; i++){
fin>>x>>y;
lista[0].push_back(i);
lista[i].push_back(0);
cap[0][i] = x;
lista[i+n].push_back(t-1);
lista[t-1].push_back(i+n);
cap[i+n][t-1] = y;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(i!=j){
lista[i].push_back(n+j);
cap[i][n+j] = 1;
lista[n+j].push_back(i);
}
int b, p, F=0;
while(true){
int parent[t];
for(int i=0; i<t; i++) parent[i] = -2;
bfs.push(0);
parent[0] = -1;
while(!bfs.empty()){
x = bfs.front();
bfs.pop();
for(auto y: lista[x])
if(parent[y] == -2 && cap[x][y]) {
parent[y] = x;
if(y == t-1) break;
bfs.push(y);
}
if(parent[t-1] != -2) break;
}
p = parent[t-1];
if(p != -2) {
b = 111;
x = t-1;
while (p != -1) {
if(cap[p][x] < b) b = cap[p][x];
x = p;
p = parent[p];
}
F += b;
x = t-1;
p = parent[x];
while (p != -1){
cap[p][x] -= b;
cap[x][p] += b;
x = p;
p = parent[p];
}
while(!bfs.empty()) bfs.pop();
}
else break;
}
fout<<F<<'\n';
for(int i=1; i<=n; i++)
for(auto j: lista[i])
if(j && !cap[i][j]) fout<<i<<" "<<j-n<<'\n';
}