Pagini recente » Cod sursa (job #1269116) | Cod sursa (job #1050680) | Cod sursa (job #2352721) | Cod sursa (job #2196118) | Cod sursa (job #2469810)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <queue>
#define DIM 5010
using namespace std;
vector<int> v[DIM];
queue<int> coada;
int n,m,x,y,z,minim,flux,nod,p,u,cap[DIM][DIM],sursa[DIM],a[DIM],v2[DIM][DIM],g;
ifstream fin("harta.in");
ofstream fout("harta.out");
int bfs(){
g=0;
memset(a,0,DIM);
a[0]=1;
coada.push(0);
while (!coada.empty()){
nod=coada.front();
for (int i=0;i<v[nod].size();i++){
int vecin=v[nod][i];
if (!a[vecin]&&cap[nod][vecin]>v2[nod][vecin]){
coada.push(vecin);
sursa[vecin]=nod;
a[vecin]=1;
// if(vecin==n)
// g=1;
}
}
coada.pop();
}
return a[2*n+1];
}
int main (){
fin>>n;
for (int i=1;i<=n;i++){
fin>>x>>y;
v[0].push_back(i);
v[i].push_back(0);
v[n+i].push_back(2*n+1);
v[2*n+1].push_back(n+i);
cap[0][i]=x;
cap[n+i][2*n+1]=y;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j){
cap[i][n+j]=1;
v[i].push_back(n+j);
v[n+j].push_back(i);
}
int sol;
while (bfs()){
for (int i=0;i<v[2*n+1].size();i++){
p=v[2*n+1][i];
if(cap[p][2*n+1]>v2[p][2*n+1]&&a[p]){
minim=cap[p][2*n+1]-v2[p][2*n+1];
u=p;
while(u!=0){
minim=min(minim,cap[sursa[u]][u]-v2[sursa[u]][u]);
u=sursa[u];
}
flux+=minim;
v2[p][2*n+1]+=minim,v2[2*n+1][p]-=minim;
u=p;
while(u!=0){
v2[sursa[u]][u]+=minim,v2[u][sursa[u]]-=minim;
u=sursa[u];
}
}
}
}
fout<<flux<<"\n";
for(int i=1;i<=n;i++)
for(int j=n+1;j<2*n+1;j++)
if(v2[i][j]==1)
fout<<i<<" "<<j-n<<"\n";
}