Pagini recente » Cod sursa (job #1515575) | Cod sursa (job #2211428) | Cod sursa (job #1218934) | Cod sursa (job #2703926) | Cod sursa (job #3128002)
#include <bits/stdc++.h>
// #define in cin
// #define out cout
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int nmax = 1e2 + 5e0;
struct edge
{
int dest, cap;
edge *rev;
edge(int dest = 0, int cap = 0) : dest(dest), cap(cap) {}
void debug()
{
cerr << dest << ' ' << cap << '\n';
}
};
int S = 0;
int D;
int n;
int sum;
vector<edge *> adj[2 * nmax];
edge edges[nmax * nmax];
int ie = 0;
void createEdge(int a, int b, int c)
{
edges[ie++] = edge(b, c);
edges[ie++] = edge(a, 0);
edges[ie - 2].rev = &edges[ie - 1];
edges[ie - 1].rev = &edges[ie - 2];
adj[a].push_back(&edges[ie - 2]);
adj[b].push_back(&edges[ie - 1]);
}
void doGraph()
{
in >> n;
D = 2 * n + 1;
for (int i = 1; i <= n; i++)
{
int a, b;
in >> a >> b;
createEdge(S, i, a);
createEdge(i + n, D, b);
sum += a;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
{
createEdge(i, n + j, 1);
}
}
}
}
bool viz[nmax * 2];
bool pump(int node)
{
//cerr << node << '\n';
if (node == D)
return 1;
viz[node] = 1;
for (auto i : adj[node])
{
int nxt = i->dest;
if (!viz[nxt] && i->cap)
{
if (pump(nxt))
{
i->cap--;
i->rev->cap++;
return 1;
}
}
}
return 0;
}
void solve()
{
for (int i = 0; i < sum; i++)
{
memset(viz, 0, sizeof viz);
pump(S);
}
}
void printSolution()
{
out << sum << '\n';
for (int i = 1; i <= n; i++)
{
for (auto e : adj[i])
{
if (e->dest > n && e->cap == 0)
{
out << i << ' ' << e->dest - n << '\n';
}
}
}
}
int main()
{
doGraph();
solve();
printSolution();
}