Pagini recente » Borderou de evaluare (job #2057428) | Cod sursa (job #706213) | Cod sursa (job #2259542) | Cod sursa (job #3275699) | Cod sursa (job #931080)
Cod sursa(job #931080)
#include <cstdio>
#include <queue>
#include <cstring>
#define NMAX 202
using namespace std;
int C[NMAX][NMAX];
int F[NMAX][NMAX];
int Graf[NMAX][NMAX];
int vizitat[NMAX];
int father[NMAX];
int gradin[NMAX];
int gradext[NMAX];
queue < int > q;
int capacitate_reziduala;
int n,flow,D,S;
inline void citesc(){
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
for(register int i=1;i<=n;++i)
scanf("%d%d",&gradin[i],&gradext[i]);
}
bool BFS(){
memset(vizitat,0,sizeof(vizitat));
q.push(0);
vizitat[0] = 1;
int nod;
while(!q.empty()){
nod = q.front();
q.pop();
if(nod == D) continue;
for(register int i=0;i<=D;++i)
if(Graf[nod][i])
if(!vizitat[i] && C[nod][i] >F[nod][i]){
vizitat[i] = 1;
father[i] = nod;
q.push(i);
}
}
return vizitat[D];
}
inline void Dinic(){
int nod;
while(BFS())
for(register int i=n+1;i<D;++i)
if(vizitat[i] && C[i][D]!=F[i][D]){
capacitate_reziduala = C[i][D] - F[i][D];
for(nod = i;nod!=0;nod=father[nod])
capacitate_reziduala = min(capacitate_reziduala,C[father[nod]][nod] - F[father[nod]][nod]);
if(capacitate_reziduala){
flow+=capacitate_reziduala;
F[i][D]+=capacitate_reziduala;
F[D][i]-=capacitate_reziduala;
for(nod = i;nod!=0;nod = father[nod]){
F[father[nod]][nod]+=capacitate_reziduala;
F[nod][father[nod]]-=capacitate_reziduala;
}}
}
}
inline void solve(){
for(register int i=1;i<=n;++i)
for(register int j=n+1;j<=2*n;++j)
Graf[i][j] = Graf[j][i] = 1 , C[i][j] = 1;
for(register int i=1;i<=n;++i)
Graf[i][i+n] = 0;
S = 0;
D = 2*n+1;
for(register int i=1;i<=n;++i){
Graf[S][i] = Graf[i][S] =1;
C[S][i] = gradin[i];
Graf[i+n][D] = Graf[i+n][D] =1;
C[i+n][D] = gradext[i];
}
Dinic();
printf("%d\n",flow);
for(register int i=1;i<=n;++i)
for(register int j=n+1;j<D;++j)
if(F[i][j])
printf("%d %d\n",i,j-n);
}
int main(){
citesc();
solve();
return 0;
}