Pagini recente » Cod sursa (job #81859) | Cod sursa (job #1462310) | Cod sursa (job #1868370) | Cod sursa (job #2243951) | Cod sursa (job #3262771)
#include <bits/stdc++.h>
using namespace std;
struct Dinic
{
struct Edge
{
int from, to, cap, prev;
};
int n;
const int inf = 1e9;
vector<Edge> edge;
vector<int> dist, prec, cprec;
Dinic(int N)
{
n = N;
dist.resize(n + 1, 0);
prec.resize(n + 1, -1);
cprec.resize(n + 1, -1);
}
void baga(int from, int to, int cap)
{
edge.push_back({from, to, cap, prec[from]});
prec[from] = edge.size() - 1;
edge.push_back({to, from, 0, prec[to]});
prec[to] = edge.size() - 1;
}
bool bfs(int s, int d)
{
dist.assign(n + 1, inf);
prec = cprec;
dist[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = prec[x]; i != -1; i = edge[i].prev)
{
if(dist[edge[i].to] == inf && edge[i].cap > 0)
{
dist[edge[i].to] = dist[x] + 1;
q.push(edge[i].to);
}
}
}
return dist[d] != inf;
}
int dfs(int x, int d, int push)
{
if(push == 0)
return 0;
if(x == d)
return push;
int ret = 0;
for(int i = prec[x]; i != -1; i = edge[i].prev)
{
if(push == 0)
break;
prec[x] = i;
if(edge[i].cap > 0 && dist[edge[i].to] == dist[x] + 1)
{
int y = dfs(edge[i].to, d, min(push, edge[i].cap));
ret += y;
push -= y;
edge[i].cap -= y;
edge[i ^ 1].cap += y;
}
}
return ret;
}
int maxFlow(int s, int d)
{
cprec = prec;
int ans = 0;
while(bfs(s, d))
ans += dfs(s, d, inf);
return ans;
}
};
int main()
{
ifstream cin("harta.in");
ofstream cout("harta.out");
int n;
cin >> n;
Dinic g(2 * n + 2);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i != j)
g.baga(i, j + n, 1);
for(int i = 1; i <= n; i ++)
{
int x, y;
cin >> x >> y;
g.baga(0, i, x);
g.baga(i + n, 2 * n + 1, y);
}
cout << g.maxFlow(0, 2 * n + 1) << '\n';
for(int i = 0; i < 2 * n * (n - 1); i += 2)
if(g.edge[i].cap == 0)
cout << g.edge[i].from << " " << g.edge[i].to - n << '\n';
}