Pagini recente » Cod sursa (job #3185479) | Cod sursa (job #2266256) | Cod sursa (job #2908983) | Cod sursa (job #2141405) | Cod sursa (job #2958587)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int cty[202][202], fl[202][202];
int tata[202];
vector <int> viz;
vector <vector <int>> adjL;
int n, nr1, nr2, i, j, flow, minn;
int BFS(){
queue<int> q;
q.push(0);
viz.assign(n+n+2, 0);
viz[0] = 1;
while(!q.empty()){
nr1 = q.front();
q.pop();
if(nr1 == n+n+1)
break;
for(auto &i : adjL[nr1]){
if (!viz[i] && fl[nr1][i] != cty[nr1][i]){
viz[i] = 1;
tata[i] = nr1;
q.push(i);
}
}
}
return viz[n];
}
int main()
{
fin >> n;
adjL.resize(n*2+2);
for (i = 1; i <= n; ++i){
fin >> nr1 >> nr2;
cty[0][i] = nr1;
cty[i+n][n+n+1] = nr2;
adjL[0].push_back(i);
adjL[i].push_back(0);
adjL[n+n+1].push_back(i+n);
adjL[i+n].push_back(n+n+1);
for (j = 1; j <= n; ++j){
if (i != j){
cty[i][j+n] = 1;
adjL[i].push_back(j+n);
adjL[j+n].push_back(i);
cty[j+n][i];
}
}
}
flow = 0;
while(BFS()){
for(auto &i:adjL[n+n+1]){
minn = INT_MAX;
tata[n+n+1] = i;
j = n + n + 1;
while(j > 0){
minn = min(minn, cty[tata[j]][j] - fl[tata[j]][j]);
j = tata[j];
}
for (j = n + n + 1; j> 0; j = tata[j]){
fl[tata[j]][j] += minn;
fl[j][tata[j]] -= minn;
}
flow += minn;
}
}
fout << flow << '\n';
for (i = 1; i <= n; ++i){
for (auto k: adjL[i]){
if (k != 0 && fl[i][k])
fout << i << ' ' << k -n << '\n';
}
}
return 0;
}