Pagini recente » Cod sursa (job #2932225) | Cod sursa (job #2949043) | Cod sursa (job #305958) | Cod sursa (job #2960205) | Cod sursa (job #2416069)
#include <bits/stdc++.h>
using namespace std;
ifstream si("harta.in");
ofstream so("harta.out");
int n, dist[205], tata[205], cap[205][205];
vector<pair<int, int> > ans;
vector<int> v[205];
bool dijkstra() {
memset(dist, 127, sizeof(dist));
memset(tata, 0, sizeof(tata));
queue<int>q;
q.push(0);
dist[0]=0;
while(q.size()) {
int x=q.front();
q.pop();
if(x==2*n+1)
break;
for(auto it:v[x])
if(cap[x][it]) {
if(dist[it]>dist[x]+1) {
dist[it]=dist[x]+1;
tata[it]=x;
q.push(it);
}
}
}
if(dist[2*n+1]>=1e9)
return 0;
int flx=1e9;
for(int x=2*n+1; x; x=tata[x])
flx=min(flx, cap[tata[x]][x]);
for(int x=2*n+1; x; x=tata[x]) {
cap[tata[x]][x]-=flx;
cap[x][tata[x]]+=flx;
}
return 1;
}
int main()
{
si>>n;
for(int i=1; i<=n; ++i) {
int a, b;
si>>a>>b;
v[0].push_back(i);
v[i].push_back(0);
cap[0][i]=a;
v[i+n].push_back(2*n+1);
v[2*n+1].push_back(i+n);
cap[i+n][2*n+1]=b;
}
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j)
if(i!=j) {
v[i].push_back(j+n);
v[j+n].push_back(i);
cap[i][j+n]=1;
}
}
while(dijkstra());
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
if(i!=j)
if(!cap[i][j+n])
ans.push_back({i,j});
}
}
so<<ans.size()<<'\n';
for(auto it:ans) {
so<<it.first<<' '<<it.second<<'\n';
}
return 0;
}