Pagini recente » Cod sursa (job #719123) | Cod sursa (job #950999) | Cod sursa (job #2206110) | Cod sursa (job #1204423) | Cod sursa (job #219577)
Cod sursa(job #219577)
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int n_max = 210;
int v[n_max][n_max];
int vaz[n_max];
int dev = 0, sup, n, sum; // Super nodes
void make_graph() //Initializing vertices of capaciy 1
{
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
if (i!=j)
{
v[i][n+j] = 1;
v[n+j][i] = 0;
}
}
int bf() // Searches and finds a path in the flux network
{
queue < int > q;
int x;
q.push(dev); // Initializing the main thing
memset(vaz,0xff,sizeof(vaz)); // Setting everything to -1
while (!q.empty())
{
x = q.front();
if (x == sup)
break;
for (int i = 0; i <= sup; ++ i)
if (vaz[i]== -1 && v[x][i] > 0)
{
vaz[i] = x;
q.push(i);
}
q.pop();
}
if (x != sup)
return 0;
// Creating the flux
while (x != dev)
{
--v[vaz[x]][x]; //Erasing only 1 cause that's the maximum possible
++v[x][vaz[x]];
x = vaz[x];
}
return 1;
}
int main()
{
int a, b;
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d", &n);
memset(v,0xff,sizeof(v));
sup = 2*n+1;
make_graph();
for (int i = 1; i <= n; ++ i)
{
scanf("%d %d", &a, &b);
v[0][i] = a;
v[i+n][sup] = b;
sum +=a;
}
int safety = 0;
while (bf())
++safety;
// if (safety!=sum)
// printf("Error\n");
printf("%d\n", sum);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
if (v[i][n+j] == 0)
printf("%d %d\n", i,j);
return 0;
}