Pagini recente » Cod sursa (job #2462541) | Cod sursa (job #971769) | Cod sursa (job #613175) | Cod sursa (job #2282415) | Cod sursa (job #3188924)
#include <bits/stdc++.h>
using namespace std;
int const nMax = 2 * 100 + 5;
int const flowMax = 110000 + 5;
int n, m, in, out, k, g;
struct nod{
int ind;
int fSent;
};
vector <vector<nod>> graph(nMax);
int findCostPath(int s, int t, vector<int>& f){
int x = t;
int ans = flowMax;
while (x != s)
{
int dad = f[x];
for(auto elm: graph[dad])
if(elm.ind == x){
ans = min(ans, elm.fSent);
if(ans == 0)
return 0;
break;
}
x = dad;
}
x = t;
while (x != s)
{
int dad = f[x];
for(auto& elm: graph[x])
if(elm.ind == dad){
elm.fSent += ans;
break;
}
for(auto& elm: graph[dad])
if(elm.ind == x){
elm.fSent -= ans;
break;
}
x = dad;
}
return ans;
}
int findPath(int s, int t){
vector <int> f(2*n+2, 0);
vector <bool> viz(2*n+2, false);
queue <int> q;
int ans = 0;
q.push(s);
viz[s] = true;
while (!q.empty())
{
int x = q.front();
q.pop();
// cout << x << "* ";
for(auto elm: graph[x]){
if(!viz[elm.ind] && elm.fSent > 0){
f[elm.ind] = x;
if(elm.ind == t){
ans += findCostPath(s, t, f);
// for(int i = s; i < t; i++){
// cout << i << ": ";
// for(auto elm: graph[i]){
// cout << elm.ind << " " << elm.fSent << ", ";
// }
// cout << "\n";
// }
}
else{
q.push(elm.ind);
viz[elm.ind] = true;
}
}
}
}
// cout << ans << " ";
return ans;
}
int fluxMax(int s, int t){
int maxPush = 0;
int ans = 0;
do
{
maxPush = findPath(s, t);
ans += maxPush;
} while (maxPush);
return ans;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
int s = 0;
int t = 2*n+1;
for(int i = 1; i <= n; i++){
cin >> in >> out;
graph[s].push_back({i, in});
graph[i].push_back({s, 0});
graph[i+n].push_back({t, out});
graph[t].push_back({i+n, 0});
}
for(int i = 1; i <=n; i++){
for(int j = 1; j<= n; j++){
if(i != j){
graph[i].push_back({n+j, 1});
graph[n+j].push_back({i, 0});
}
}
}
// for(int i = s; i < t; i++){
// cout << i << ": ";
// for(auto elm: graph[i]){
// cout << elm.ind << " " << elm.fSent << ", ";
// }
// cout << "\n";
// }
// cout << "\n\n";
cout << fluxMax(s, t) << "\n";
for(int i = 1; i <= n; i++){
for(auto elm: graph[i]){
if(elm.ind-n != i && elm.fSent == 0 && elm.ind-n > 0)
cout << i << " " << elm.ind-n << "\n";
}
}
return 0;
}