Pagini recente » Cod sursa (job #662858) | Cod sursa (job #1061909) | Cod sursa (job #296588) | Cod sursa (job #578931) | Cod sursa (job #1162436)
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#define per pair<int,int>
#define DN 205
#define x first
#define y second
#define pb push_back
#define INF (1<<30)
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,S,D,C[DN][DN],F[DN][DN],t[DN],arb[DN],flow;
vector < int > list[DN];
bitset < DN > viz;
void read(){
f>>n;
S = 0; D = n + n + 1;
for(int i=1;i<=n;++i){
int a,b;
f>>a>>b;
C[S][i] = a;
C[n + i][D] = b;
list[S].pb(i);
list[i].pb(S);
list[n + i].pb(D);
list[D].pb(n + i);
}
}
void build_graph(){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j){
list[i].pb(n+j);
list[n +j].pb(i);
C[i][n + j] = 1;
}
}
bool bf(){
viz&=0;
arb[0] = 1;
arb[1] = S;
viz[S] = 1;
for(int i=1;i<=arb[0];++i){
int nod = arb[i];
if( nod == D )
continue;
for(int j=0;j<list[nod].size();++j){
int next_nod = list[nod][j];
if( C[nod][next_nod] == F[nod][next_nod] || viz[next_nod]) continue;
viz[next_nod] = 1;
arb[ ++arb[0]] = next_nod;
t[next_nod] = nod;
}
}
return viz[D];
}
void solve(){
bool exista_flux = true;
for(;exista_flux;){
exista_flux = bf();
for(int i=n + 1;i<=n + n;++i){ /// iau vecinii destinatiei
int nod = i, fmin = INF;
if(C[nod][D] == F[nod][D] || !viz[nod])
continue;
t[ D ] = nod;
for( nod = D ; nod!=S ; nod = t[nod])
fmin=min(fmin,C[ t[nod] ][ nod ] - F[ t[nod] ][ nod ] );
if(fmin == 0)
continue;
for( nod = D; nod!=S ; nod = t[nod]){
F[ t[nod] ][ nod ] += fmin;
F[ nod ][ t[nod] ] -= fmin;
}
flow+=fmin;
}
}
}
void write(){
g<<flow<<"\n";
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(F[i][n + j])
g<<i<<" "<<j<<endl;
}
int main()
{
read();
build_graph();
solve();
write();
return 0;
}