Pagini recente » Cod sursa (job #6569) | Cod sursa (job #584952) | Cod sursa (job #314871) | Cod sursa (job #880431) | Cod sursa (job #3189596)
#include <fstream>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <ctime>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
#define ll long long
const ll INF = 1e18;
struct Dinic {
int n, s, t;
vector<int> dist;
vector<int> done;
vector<vector<int>> g;
vector<vector<ll>> cap, flow;
Dinic(int _n = 0) {
n = _n + 10;
g.resize(n + 1);
cap.resize(n + 1, vector<ll>(n + 1));
flow.resize(n + 1, vector<ll>(n + 1));
}
void init(int _n) {
n = _n + 10;
g.resize(n + 1);
cap.resize(n + 1, vector<ll>(n + 1));
flow.resize(n + 1, vector<ll>(n + 1));
}
void add_edge(int u, int v, ll w) {
g[u].push_back(v);
g[v].push_back(u);
cap[u][v] = w;
}
bool bfs() {
dist.assign(n, -1);
dist[s] = 0;
queue <int> q;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for (auto &v : g[u]) {
if (dist[v] == -1 && cap[u][v] > flow[u][v])
dist[v] = dist[u] + 1, q.push(v);
}
}
if (dist[t] != -1)
return 1;
return 0;
}
ll dfs(int u, ll _flow) {
if (u == t) {
return _flow;
}
for (int &i = done[u]; i < g[u].size(); i++) {
int v = g[u][i];
if (cap[u][v] <= flow[u][v])
continue;
if (dist[v] == dist[u] + 1) {
ll nw = dfs(v, min(_flow, cap[u][v] - flow[u][v]));
if (nw > 0) {
flow[u][v] += nw;
flow[v][u] -= nw;
return nw;
}
}
}
return 0;
}
ll max_flow(int _s, int _t) {
s = _s;
t = _t;
ll _flow = 0;
while (bfs()) {
done.assign(n, 0);
while(ll nw = dfs(s, INF)) {
_flow += nw;
}
}
return _flow;
}
} d;
int in[101];
int out[101];
int n, s, t;
void read() {
ifstream f("harta.in");
f >> n;
for (int i = 1; i <= n; i++)
f >> out[i] >> in[i];
f.close();
}
void solve() {
d.init(2 * n + 10);
s = 2 * n + 1;
t = 2 * n + 2;
for (int i = 1; i <= n; i++) {
d.add_edge(s, i, out[i]);
d.add_edge(i + n, t, in[i]);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i == j)
continue;
d.add_edge(i, j + n, 1);
}
}
void output() {
ofstream g("harta.out");
g << d.max_flow(s, t) << '\n';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i == j)
continue;
if (d.flow[i][j + n] == 1)
g << i << ' ' << j << '\n';
}
g.close();
}
int main() {
read();
solve();
output();
return 0;
}