Pagini recente » Istoria paginii runda/dedicatie_speciala6/clasament | Istoria paginii preoni-2007/runda-finala/poze/la-masa | Cod sursa (job #1950875)
#include <bits/stdc++.h>
#define maxN 204
#define inf 1000000000
using namespace std;
FILE *fin = freopen("harta.in", "r", stdin);
FILE *fout = freopen("harta.out", "w", stdout);
/* ================== */
int n, m, N;
/* ================== */
int S, D, r[maxN][maxN], deUnde[maxN];
queue < int > Q;
/* ================== */
int ans;
void BFS(int S, int D)
{
int i;
memset(deUnde, 0, sizeof(deUnde));
Q.push(S);
deUnde[S] = S;
deUnde[D] = D;
while (!Q.empty())
{
int x = Q.front();
Q.pop();
for (i = 1; i <= N; ++ i)
if (r[x][i] > 0 && deUnde[i] == 0)
{
deUnde[i] = x;
Q.push(i);
}
}
}
void maxFlow()
{
ans = 0;
bool continua = true;
while (continua)
{
BFS(S, D);
continua = false;
for(int u = 1; u <= N; u++)
if (r[u][D] > 0 && deUnde[u] != 0 && u != D)
{
continua = true;
deUnde[D] = u;
int nod = D;
int cap = inf;
while (nod != S)
{
cap = min(cap, r[deUnde[nod]][nod]);
nod = deUnde[nod];
}
nod = D;
ans += cap;
while (nod != S)
{
r[deUnde[nod]][nod] -= cap;
r[nod][deUnde[nod]] += cap;
nod = deUnde[nod];
}
}
}
}
int main()
{
scanf("%d", &n);
S = 1;
D = N = 2 * n + 2;
for (int i = 1; i <= n; ++ i)
{
int gIn, gOut;
scanf("%d %d", &gIn, &gOut);
m += gIn + gOut;
r[S][i * 2 + 1] = gIn;
r[i * 2][D] = gOut;
}
for (int i = 1; i <= n; ++ i)
for (int j = i + 1; j <= n; ++ j)
r[i * 2 + 1][j * 2] = r[j * 2 + 1][i * 2] = 1;
maxFlow();
printf("%d\n", m / 2);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
if (i != j && !r[i * 2 + 1][j * 2])
printf("%d %d\n", i, j);
return 0;
}