Pagini recente » Cod sursa (job #215027) | Cod sursa (job #1312840) | Cod sursa (job #662642) | Cod sursa (job #82357) | Cod sursa (job #991941)
Cod sursa(job #991941)
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 102;
#define FILEIN "harta.in"
#define FILEOUT "harta.out"
vector<int> A[2*NMAX];
int cap[2*NMAX][2*NMAX];
int flow[2*NMAX][2*NMAX];
int t[2*NMAX];
int N, M, s, d;
bool mark[2*NMAX];
vector< pair<int, int> > sol;
bool bfs() {
queue<int> Q;
memset(mark, 0, sizeof(mark));
Q.push(s);
while(!Q.empty()) {
int nod = Q.front(); Q.pop();
if ( nod == d ) continue;
for ( size_t j = 0; j < A[nod].size(); j++) {
int next = A[nod][j];
if (cap[nod][next] == flow[nod][next] || mark[next]) continue;
mark[next] = 1;
Q.push(next);
t[next] = nod;
}
}
return mark[d];
}
int detfmin(int nod) {
int f = 0x3f3f3f3f;
for ( nod = d; nod != s; nod = t[nod]) {
f = min(f, cap[t[nod]][nod] - flow[t[nod]][nod]);
}
return f;
}
void rmfmin(int nod, int f) {
for ( nod = d; nod != s; nod = t[nod]) {
flow[t[nod]][nod] += f;
flow[nod][t[nod]] -= f;
}
}
int main() {
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
scanf("%d", &N);
s = 0;
d = 2 * N + 1;
for ( int i = 1, x, y; i <= N; i++ ) {
scanf("%d %d", &x, &y);
A[s].push_back(i), A[i].push_back(s), cap[s][i] = x;
A[d].push_back(N+i), A[N+i].push_back(d), cap[N+i][d] = y;
}
for ( int i = 1; i <= N; i++) {
for ( int j = 1; j <= N; j++) {
if ( i != j ) {
A[i].push_back(N+j);
A[N+j].push_back(i);
cap[i][N+j] = 1;
}
}
}
while(bfs()) {
for ( int i = 0; i < A[d].size(); i++) {
int nod = A[d][i];
if (flow[nod][d] == cap[nod][d] || !mark[nod]) continue;
t[d] = nod;
int fminim = detfmin(nod);
if (!fminim)
continue;
rmfmin(nod, fminim);
}
}
for ( int i = 1; i <= N; i++) {
for ( int j = 1; j <= N; j++) {
if ( flow[i][N+j] ) {
++M;
sol.push_back(make_pair(i, j));
}
}
}
printf("%d\n", M);
for ( int i = 0; i < M; i++) {
printf("%d %d\n", sol[i].first, sol[i].second);
}
return 0;
}