Pagini recente » Cod sursa (job #2962145) | Cod sursa (job #162697) | Cod sursa (job #2040042) | Cod sursa (job #1275335) | Cod sursa (job #2836103)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct Graph
{
vector<vector<int> > cap, G;
vector<int> dad;
int n;
Graph(int _n): n(_n), dad(_n + 1)
{
cap = vector<vector<int> >(n + 1, vector<int>(n + 1));
G = vector<vector<int> >(n + 1, vector<int>(n + 1));
}
inline void AddEdge(int x, int y, int val){
G[x].push_back(y);
G[y].push_back(x);
cap[x][y] += val;
}
inline int BFS()
{
fill(dad.begin(), dad.end(), -1);
dad[0] = 0;
queue<int> q;
q.push(0);
while(!q.empty())
{
int nd = q.front();
q.pop();
if(nd == n)
continue;
for(auto it: G[nd])
if(dad[it] == -1 && cap[nd][it])
{
dad[it] = nd;
q.push(it);
}
}
return dad[n];
}
inline int MaxFlow()
{
int flow(0), flowmax(0);
while(BFS() != -1)
{
for(auto it: G[n])
if(dad[it] != -1 && cap[it][n])
{
dad[n] = it;
flow = (1 << 30);
int x = n;
while(x != 0)
{
flow = min(flow, cap[dad[x]][x]);
x = dad[x];
}
if(flow == 0 || flow == (1 << 30))
continue;
x = n;
while(x != 0)
{
cap[dad[x]][x] -= flow;
cap[x][dad[x]] += flow;
x = dad[x];
}
flowmax += flow;
}
}
return flowmax;
}
};
int main()
{
int n;
fin >> n;
Graph G(2 * n + 1);
for(int i = 1; i <= n; ++i){
int in, out;
fin >> in >> out;
G.AddEdge(0, i, in);
G.AddEdge(i + n, 2 * n + 1, out);
for(int j = 1; j <= n; ++j)
if(i != j)
G.AddEdge(i, j + n, 1);
}
fout << G.MaxFlow() << '\n';
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(i != j && G.cap[i + n][j])
fout << j << ' ' << i << '\n';
return 0;
}