Pagini recente » Cod sursa (job #1696943) | Cod sursa (job #2204469) | Cod sursa (job #1235246) | Cod sursa (job #858558) | Cod sursa (job #1741168)
#include <fstream>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string>
#define pb push_back
#define NMAX 205
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int in[NMAX],out[NMAX],C[NMAX][NMAX],F[NMAX][NMAX],viz[NMAX],Prev[NMAX],sink;
vector<int> v[NMAX];
int BFS() {
int i,x,y;
queue<int> Q;
memset(viz,0,sizeof(viz));
viz[0]=1;
Q.push(0);
while(!Q.empty()) {
x=Q.front();
Q.pop();
//if(x==sink) return 1;
for(i=0;i<v[x].size();++i) {
y=v[x][i];
if(!viz[y] && C[x][y] > F[x][y]) {
Prev[y]=x;
viz[y]=1;
Q.push(y);
}
}
}
return viz[sink];
}
int main() {
int n,i,j,x,y,q,m=0,fmin,p;
fin>>n;
sink=2*n+1;
for(i=1;i<=n;++i) {
fin>>out[i]>>in[i];
m+=out[i];
v[0].pb(i);
v[i+n].pb(sink);
C[0][i]=in[i];
C[i+n][sink]=out[i];
}
for(i=1;i<=n;++i) {
for(j=n+1;j<sink;++j) {
if(i==j-n) continue;
C[i][j]=1;
v[j].pb(i);
v[i].pb(j);
}
}
while(BFS()) {
p=sink;
while(p!=0) {
++F[Prev[p]][p];
--F[p][Prev[p]];
p=Prev[p];
}
}
fout<<m<<'\n';
for(i=1;i<=n;++i)
for(j=n+1;j<sink;++j)
if(F[i][j]==1)
fout<<j-n<<' '<<i<<'\n';
return 0;
}