Pagini recente » Clasament srymwgerhd | Cod sursa (job #2555063) | Cod sursa (job #1889877) | Cod sursa (job #1100752) | Cod sursa (job #1830134)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
class InputReader {
public:
InputReader() {}
InputReader(const char *file_name) {
input_file = fopen(file_name, "r");
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
inline InputReader &operator >>(int &n) {
while (buffer[cursor] < '0' || buffer[cursor] > '9') {
advance();
}
n = 0;
while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
n = n * 10 + buffer[cursor] - '0';
advance();
}
return *this;
}
private:
FILE *input_file;
static const int SIZE = 1 << 17;
int cursor;
char buffer[SIZE];
inline void advance() {
++ cursor;
if (cursor == SIZE) {
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
}
};
InputReader cin ("harta.in");
ofstream cout ("harta.out");
const int MaxN = 205, Inf = 0x3f3f3f3f;
vector <int> G[MaxN];
queue <int> Q;
int n, m, Source, Destination;
int Capacity[MaxN][MaxN], Flow[MaxN][MaxN], father[MaxN];
inline void ClearQ() {
while (Q.size()) {
Q.pop();
}
}
bool Bfs() {
ClearQ();
memset(father, 0, sizeof father);
father[Source] = -1;
Q.push(Source);
while (Q.size()) {
int node = Q.front();
Q.pop();
if (node == Destination) {
continue;
}
for (auto nxt: G[node]) {
if (father[nxt] or !(Capacity[node][nxt] - Flow[node][nxt])) {
continue;
}
Q.push(nxt);
father[nxt] = node;
}
}
return (bool) father[Destination];
}
inline int CalcFlow(int node = Destination) {
int ans = Inf;
while (father[node] != -1) {
int parent = father[node];
ans = min(ans, Capacity[parent][node] - Flow[parent][node]);
node = parent;
}
return ans;
}
inline void UpdateFlow(int Quantity, int node = Destination) {
while (father[node] != -1) {
int parent = father[node];
Flow[parent][node] += Quantity;
Flow[node][parent] -= Quantity;
node = parent;
}
}
int main() {
cin >> n;
Source = 0;
Destination = 2 * n + 1;
for (int i = 1; i <= n; ++i) {
int a, b;
cin >> a >> b;
m += a;
G[Source].push_back(i);
G[i].push_back(Source);
Capacity[Source][i] = a;
G[n + i].push_back(Destination);
G[Destination].push_back(n + i);
Capacity[n + i][Destination] = b;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) {
continue;
}
G[i].push_back(n + j);
G[n + j].push_back(i);
Capacity[i][n + j] = 1;
}
}
while (Bfs()) {
for (auto nxt: G[Destination]) {
if (!(Capacity[nxt][Destination] - Flow[nxt][Destination]) or !father[nxt]) {
continue;
}
father[Destination] = nxt;
int Quantity = CalcFlow();
if (Quantity) {
UpdateFlow(Quantity);
}
}
}
cout << m << '\n';
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
//cout << "[" << i << "][" << j << "] = " << Flow[i][n + j] << '\n';
if (Flow[i][n + j] == 1) {
cout << i << ' ' << j << '\n';
}
}
}
return 0;
}