Pagini recente » Cod sursa (job #698933) | Cod sursa (job #1133991) | Cod sursa (job #1456985) | Cod sursa (job #1492543) | Cod sursa (job #3128001)
#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[nmax];
edge edges[nmax*3];
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();
}