Pagini recente » Cod sursa (job #694090) | Cod sursa (job #821660) | Cod sursa (job #1656626) | Istoria paginii runda/ghiocel/clasament | Cod sursa (job #2180466)
#include <fstream>
#include <vector>
#include <queue>
#define DIM 102
using namespace std;
ifstream in ("harta.in");
ofstream out("harta.out");
int n, t[DIM];
struct node{
int in, out;
}nod[DIM];
vector<int> graf[DIM];
int Cap[DIM][DIM], Flow[DIM][DIM];
bool viz[DIM];
queue<int> q;
bool bfs(){
for(int i = 0; i <= 2 * n + 1; ++ i)
viz[i] = false;
viz[0] = true;
q.push(0);
while(!q.empty()){
int nod = q.front();
q.pop();
for(int i = 0; i < graf[nod].size(); ++ i){
int nodc = graf[nod][i];
if(!viz[nodc] && Cap[nod][nodc] > Flow[nod][nodc]){
viz[nodc] = true;
q.push(nodc);
t[nodc] = nod;
}
}
}
return viz[2 * n + 1];
}
int main(int argc, const char * argv[]) {
in>>n;
for(int i = 1; i <= n; ++ i)
in>>nod[i].in>>nod[i].out;
for(int i = 1; i <= n; ++ i){
graf[0].push_back(i);
graf[i].push_back(0);
Cap[0][i] = nod[i].in;
for(int j = n + 1; j <= 2 * n; ++ j)
if(j - i == n)
continue;
else{
graf[i].push_back(j);
graf[j].push_back(i);
Cap[i][j] = 1;
}
}
for(int i = n + 1; i <= 2 * n; ++ i){
graf[i].push_back(2 * n + 1);
graf[2 * n + 1].push_back(i);
Cap[i][2 * n + 1] = nod[i - n].out;
}
while(bfs()){
int N = 2 * n + 1;
for(int i = 0; i < graf[N].size(); ++ i){
int nod = graf[N][i];
if(!viz[nod] || Cap[nod][N] <= Flow[nod][N]) continue;
int minim = Cap[nod][N] - Flow[nod][N];
while(nod != 0){
minim = min(minim, Cap[t[nod]][nod] - Flow[t[nod]][nod]);
nod = t[nod];
}
nod = graf[N][i];
Flow[nod][N] += minim;
Flow[N][nod] -= minim;
while(nod != 0){
Flow[t[nod]][nod] += minim;
Flow[nod][t[nod]] -= minim;
nod = t[nod];
}
}
}
int nr = 0;
for(int i = 1; i <= n; ++ i){
for(int j = n + 1; j <= 2 * n; ++ j){
if(Flow[i][j] > 0)
++ nr;
}
}
out<<nr<<'\n';
for(int i = 1; i <= n; ++ i){
for(int j = n + 1; j <= 2 * n; ++ j){
if(Flow[i][j] > 0)
out<<i<<" "<<j - n<<'\n';
}
}
return 0;
}