Pagini recente » Cod sursa (job #508426) | Cod sursa (job #2984633) | Cod sursa (job #2352063) | Cod sursa (job #2065625) | Cod sursa (job #2596499)
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 100;
const int INF = 2.e9;
int cf[2 * NMAX + 5][2 * NMAX + 5] , viz[2 * NMAX + 5] , n , s , t;
int bfs()
{
memset(viz , -1 , sizeof(viz));
viz[s] = -2;
int u , v;
queue <int> q;
q.push(s);
while(!q.empty())
{
u = q.front();
q.pop();
if(u == t)
continue;
for(v = 0 ; v <= t ; v ++)
if(viz[v] == -1 && cf[u][v] > 0)
{
viz[v] = u;
q.push(v);
}
}
if(viz[t] == -1)
return 0;
return 1;
}
void update_flow()
{
int nod , flow;
flow = INF;
for(nod = t ; viz[nod] != -2 ; nod = viz[nod])
flow = min(flow , cf[viz[nod]][nod]);
for(nod = t ; viz[nod] != -2 ; nod = viz[nod])
{
cf[viz[nod]][nod] = cf[viz[nod]][nod] - flow;
cf[nod][viz[nod]] = cf[nod][viz[nod]] + flow;
}
}
void max_flow()
{
int nod;
while(bfs())
for(nod = n + 1 ; nod <= 2 * n ; nod ++)
{
if(viz[nod] == -1 || cf[nod][t] == 0)
continue;
viz[t] = nod;
update_flow();
}
}
int main()
{
freopen("harta.in" , "r" , stdin);
freopen("harta.out" , "w" , stdout);
int i , j , m , x , y;
scanf("%d" , &n);
m = 0;
t = 2 * n + 1;
for(i = 1 ; i <= n ; i ++)
{
scanf("%d%d" , &x , &y);
cf[s][i] = x;
cf[n + i][t] = y;
m = m + x;
}
for(i = 1 ; i <= n ; i ++)
for(j = 1 ; j <= n ; j ++)
if(i != j)
cf[i][n + j] = 1;
s = 0;
max_flow();
printf("%d\n" , m);
for(i = 1 ; i <= n ; i ++)
for(j = 1 ; j <= n ; j ++)
if(i != j && cf[i][n + j] == 0)
printf("%d %d\n" , i , j);
return 0;
}