Pagini recente » Cod sursa (job #142898) | Cod sursa (job #2693132) | Cod sursa (job #1290253) | Cod sursa (job #993684) | Cod sursa (job #791731)
Cod sursa(job #791731)
#include <fstream>
#include <vector>
#include <queue>
#define NMAx 210
using namespace std;
queue <int> Q;
vector <int> G[NMAx];
int N,S,D,paint,Sum,T[NMAx];
int viz[NMAx],Flux[NMAx][NMAx];
bool BF() {
int i,Nod,Vecin;
Q.push(S);
++paint;
viz[S]=paint;
while(!Q.empty()) {
Nod=Q.front();
Q.pop();
for(i=0;i<G[Nod].size();i++) {
Vecin=G[Nod][i];
if(Flux[Nod][Vecin]&&viz[Vecin]!=paint) {
T[Vecin]=Nod;
Q.push(Vecin);
viz[Vecin]=paint;
}
}
}
return (viz[D]==paint);
}
void BuildGraph() {
int i,j;
for(i=1;i<=N;i++)
for(j=N+1;j<D;j++)
if(i!=(j-N)) {
Flux[i][j]=1;
G[i].push_back(j);
G[j].push_back(i);
}
}
void Solve() {
int i;
BuildGraph();
while(BF()) {
for(i=D;i;i=T[i]) {
Flux[T[i]][i]--;
Flux[i][T[i]]++;
}
}
}
void Citire() {
ifstream in("harta.in");
in>>N;
S=0;
D=2*N+1;
for(int i=1;i<=N;i++) {
in>>Flux[S][i]>>Flux[i+N][D];
Sum+=Flux[S][i]+Flux[i+N][D];
G[S].push_back(i);
G[i+N].push_back(D);
}
in.close();
}
void Afis() {
int i,j;
ofstream out("harta.out");
out<<(Sum/2)<<'\n';
for(i=1;i<=N;i++)
for(j=0;j<G[i].size();j++)
if(!Flux[i][G[i][j]])
out<<i<<' '<<(G[i][j]-N)<<'\n';
out.close();
}
int main() {
Citire();
Solve();
Afis();
return 0;
}