Pagini recente » Cod sursa (job #1388071) | Cod sursa (job #1737138) | Cod sursa (job #1521269) | Cod sursa (job #975964) | Cod sursa (job #881289)
Cod sursa(job #881289)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
#define MAXN 2 * 110
#define INF 0x3f3f3f3f
#define FORIT(it, v) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
int N, M, S, D, C[MAXN][MAXN], F[MAXN][MAXN], dad[MAXN], used[MAXN];
vector<int> graph[MAXN];
bool DFS() {
queue<int> coada; coada.push(S);
memset(used, 0, sizeof(used));
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
used[nod] = 1;
if (nod == D)
continue;
FORIT(it, graph[nod]) {
if (!used[*it] && C[nod][*it] - F[nod][*it]) {
dad[*it] = nod;
coada.push(*it);
used[*it] = 1;
}
}
}
return used[D];
}
int main() {
fin >> N;
S = 0;
D = 2 * N + 1;
for (int i = 1; i <= N; ++i) {
int a, b;
fin >> a >> b;
graph[S].push_back(i); graph[i].push_back(S);
graph[i + N].push_back(D); graph[D].push_back(i + N);
C[S][i] = a;
C[i + N][D] = b;
for (int j = 1; j <= N; ++j)
if (j != i) {
graph[i].push_back(j + N);
graph[j + N].push_back(i);
C[i][j + N] = 1;
}
}
int sol = 0;
while (DFS())
FORIT(it, graph[D])
if (dad[*it] && C[*it][D] != F[*it][D]) {
dad[D] = *it;
int minim = INF;
for (int i = D; i != S; i = dad[i])
minim = min (minim, C[dad[i]][i] - F[dad[i]][i]);
sol += minim;
for (int i = D; i != S; i = dad[i]) {
F[dad[i]][i] += minim;
F[i][dad[i]] -= minim;
}
}
fout << sol << "\n";
for (int i = 1; i <= N; ++i)
for (int j = N + 1; j <= 2 * N; ++j)
if (F[i][j] == 1)
fout << i << " " << j - N << "\n";
return 0;
}