Pagini recente » Cod sursa (job #3291700) | Cod sursa (job #3217099) | Cod sursa (job #2713484) | Cod sursa (job #2717742) | Cod sursa (job #1598411)
#include <bits/stdc++.h>
#define In(node) (node)
#define Out(node) (node+100)
using namespace std;
const int Nmax = 200 + 10;
const int inf = 0x3f3f3f3f;
int n , i , j , flow , S , D;
int dad[Nmax];
int f[Nmax][Nmax] , c[Nmax][Nmax];
vector < int > g[Nmax];
queue < int > q;
void Add(int x , int y , int capacitate)
{
g[x].push_back(y);
g[y].push_back(x);
c[x][y] = capacitate;
}
bool bfs()
{
int ok = 0; dad[S] = -1;
for (q.push(S); q.size(); q.pop())
{
int node = q.front();
for (auto &it : g[node])
if (!dad[it] && c[node][it] > f[node][it])
{
if (it != D) dad[it] = node, q.push(it);
else ok = 1;
}
}
return ok;
}
void maxflow()
{
for (bool ok = bfs() ; ok ; ok = bfs())
{
for (auto &it : g[D])
if (dad[it] && c[it][D] > f[it][D])
{
dad[D] = it; int minn = inf;
for (int node = D; node != S; node = dad[node])
minn = min(minn , c[dad[node]][node] - f[dad[node]][node]);
if (minn <= 0) continue;
flow += minn;
for (int node = D; node != S; node = dad[node])
f[dad[node]][node] += minn,
f[node][dad[node]] -= minn;
}
memset(dad , 0 , sizeof(dad));
}
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d", &n); S = 201; D = 202;
for (i = 1; i <= n; ++i)
{
int c1 , c2;
scanf("%d %d", &c1, &c2);
Add(S , Out(i) , c1);
Add(In(i) , D , c2);
}
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
if (i != j)
Add(Out(i) , In(j) , 1);
maxflow();
printf("%d\n", flow);
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
if (f[Out(i)][In(j)] == 1) printf("%d %d\n", i , j);
return 0;
}