Pagini recente » Cod sursa (job #877108) | Cod sursa (job #2498284) | Cod sursa (job #502360) | Cod sursa (job #3210258) | Cod sursa (job #2661154)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 105;
const int INF = (1<<29);
int f[NMAX][NMAX],c[NMAX][NMAX],tata[NMAX];
int n,N,x,y,z,rasp=0;
bool ver[NMAX];
vector <int> v[NMAX];
queue <int> q;
bool bfs(){
for(int i=0;i<=N;i++) ver[i]=false;
ver[0]=true;
q.push(0);
while(!q.empty()){
int node=q.front();
q.pop();
for(int i=0;i<v[node].size();i++){
int vecin=v[node][i];
if(ver[vecin]==false and c[node][vecin]>f[node][vecin]){
q.push(vecin);
tata[vecin]=node;
ver[vecin]=true;
}
}
}
if(ver[N]==true) return 1;
return 0;
}
int main()
{
fin >> n;
N=2*n+1;
for(int i=1;i<=n;i++){
fin >> x >> y;
v[0].push_back(i);
v[i].push_back(0);
c[0][i]=x;
v[n+i].push_back(N);
v[N].push_back(n+i);
c[n+i][N]=y;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
v[i].push_back(n+j);
v[n+j].push_back(i);
c[i][n+j]=1;
}
}
while(bfs()==true){
for(int i=0;i<v[N].size();i++){
int nod=v[N][i];
if(ver[nod]==true and c[nod][N]>f[nod][N]){
int minim=c[nod][N]-f[nod][N];
int aux=nod;
while(aux!=0){
int t=tata[aux];
if(c[t][aux]-f[t][aux]<minim)
minim=c[t][aux]-f[t][aux];
aux=tata[aux];
}
if(minim==0) continue;
rasp+=minim;
f[nod][N]+=minim;
f[N][nod]-=minim;
aux=nod;
while(aux!=0){
int t=tata[aux];
f[t][aux]+=minim;
f[aux][t]-=minim;
aux=tata[aux];
}
}
}
}
fout << rasp << '\n';
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(f[i][j+n]==1)
fout << i << ' ' << j << '\n';
}
}
return 0;
}