Pagini recente » Cod sursa (job #1612784) | Cod sursa (job #420397) | Cod sursa (job #2435556) | Cod sursa (job #1026369) | Cod sursa (job #3189240)
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int ans[250][250];
struct Dinic {
struct edge {
int to, rev;
int flow, w;
int id;
};
int n, s, t, mxid;
vector <int> d, flow_through;
vector <int> done;
vector <vector <edge>> g;
Dinic() {}
Dinic(int _n) {
n = _n + 10;
mxid = 0;
g.resize(n);
}
void add_edge(int u, int v, int w, int id = -1) {
edge a = {v, g[v].size(), 0, w, id};
edge b = {u, g[u].size(), 0, 0, -2};
g[u].emplace_back(a);
g[v].emplace_back(b);
mxid = max(mxid, id);
}
bool bfs() {
d.assign(n, -1);
d[s] = 0;
queue <int> q;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto &e : g[u]) {
int v = e.to;
if(d[v] == -1 && e.flow < e.w)
d[v] = d[u] + 1, q.push(v);
}
}
return d[t] != -1;
}
int dfs(int u, int flow) {
if (u == t) {
return flow;
}
for(int &i = done[u]; i < g[u].size();i++) {
edge &e = g[u][i];
if(e.w <= e.flow)
continue;
int v = e.to;
if(d[v] == d[u] + 1) {
int nw = dfs(v, min(flow, e.w - e.flow));
if(nw > 0) {
e.flow += nw;
g[v][e.rev].flow -= nw;
ans[u][v] += nw;
ans[v][u] -= nw;
return nw;
}
}
}
return 0;
}
int max_flow(int _s, int _t) {
s = _s;
t = _t;
int flow = 0;
while (bfs()) {
done.assign(n, 0);
while(int nw = dfs(s, inf)) {
flow += nw;
}
}
flow_through.assign(mxid + 10, 0);
for(int i = 0; i < n; i++)
for(auto e : g[i])
if(e.id >= 0)
flow_through[e.id] = e.flow;
return flow;
}
};
int main()
{
ifstream f("harta.in");
ofstream g("harta.out");
int n, m;
f >> n;
int a[n + 5], b[n + 5], sumb = 0;
for(int i = 1; i <= n; i++) {
f >> a[i] >> b[i];
sumb += b[i];
}
Dinic G(2 * n);
int src = 2 * n + 1, trg = 2 * n + 2;
for(int i = 1; i <= n; i++) {
G.add_edge(src, i, a[i]);
G.add_edge(i + n, trg, b[i]);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i != j) {
G.add_edge(i, j + n, 1);
}
}
}
int sol = G.max_flow(src, trg);
g << sumb << "\n";
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(ans[i][j + n] == 1) {
g << i << " " << j << "\n";
}
}
}
return 0;
}