Pagini recente » Cod sursa (job #218320) | Cod sursa (job #2749851) | Cod sursa (job #2911771) | Cod sursa (job #2894473) | Cod sursa (job #1699283)
# include <bits/stdc++.h>
using namespace std;
ifstream fi("harta.in");
ofstream fo("harta.out");
# define x first
# define y second
# define ll long long
# define db long double
# define scn(x) scanf("%I64d",&x)
# define scan(x) scanf("%d",&x)
# define print(x) printf("%d ",x)
# define prnt(x) printf("%I64d ",x);
# define eol printf("\n")
int F[105][105];
int d[105];
int bfs(int n)
{
d[0] = 0;
for (int i = 1;i <= n;++i) d[i] = -1;
queue < int > Q;
Q.push(0);
while (!Q.empty() && d[n] == -1)
{
int node = Q.front();
Q.pop();
for (int i = 0;i <= n;++i)
if (d[i] == -1 && F[node][i])
Q.push(i),d[i] = node;
}
if (d[n] == -1) return 0;
int flow = 1e9;
for (int vertex = n;vertex;vertex = d[vertex])
flow = min(flow,F[d[vertex]][vertex]);
for (int vertex = n;vertex;vertex = d[vertex])
F[d[vertex]][vertex] -= flow,F[vertex][d[vertex]] += flow;
return flow;
}
int main(void)
{
int n;
fi>>n;
int Sum = 0;
for (int i = 1;i <= n;++i)
{
int a,b;
fi>>a>>b;
Sum += a;
F[0][i] = a;
F[i+n][n+n+1] = b;
}
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j)
if (i != j) F[i][j+n] = 1;
int flow = 0,cnt = 0;
while ((cnt = bfs(n+n+1)) != 0) flow += cnt;
assert(Sum == flow);
vector < pair < int , int > > ans;
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j)
if (!F[i][j+n] && F[j][i+n]) ans.push_back({i,j});
fo << (ans.size()) << '\n';
for (auto it : ans) fo << it.x << ' ' << it.y << '\n';
return 0;
}