Pagini recente » Cod sursa (job #698561) | Cod sursa (job #1542932) | Cod sursa (job #1703819) | Cod sursa (job #1951319) | Cod sursa (job #1444515)
#include <fstream>
#include <cstring>
#include <vector>
#define vint vector<int>::iterator
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n,m,x,y;
int C[301][301],F[301][301],viz[301],q[301],T[301];
vector<int> G[301];
struct edge
{
int x,y;
}e[90001];
bool bfs (int x)
{
memset (viz,0,sizeof(viz));
viz[x] = 1;
int l = 1;
q[l] = x;
for (int s=1; s<=l; ++s)
{
x = q[s];
for (vint it = G[x].begin (); it != G[x].end (); ++it)
{
if (!viz[*it] && C[x][*it] != F[x][*it])
{
viz[*it] = 1;
q[++l] = *it;
T[*it] = x;
}
}
}
return viz[n];
}
int main()
{
fin>>n;
for (int i=1; i<=n; ++i)
{
fin>>x>>y;
C[0][i] = x;
C[i+n][2*n+1] = y;
G[0].push_back (i);
G[i].push_back (0);
G[i+n].push_back (2*n+1);
G[2*n+1].push_back (i+n);
for (int j=1; j<=n; ++j)
{
if (i != j)
{
G[i].push_back (j+n);
G[j+n].push_back (i);
C[i][j+n] = 1;
}
}
}
int nn = n;
n = 2*n+1;
while (bfs (0))
{
for (vint it = G[n].begin (); it != G[n].end(); ++it)
{
if (!viz[*it] || C[*it][n] == F[*it][n])
continue;
int minf = C[*it][n] - F[*it][n];
for (int i = *it; i != 0; i = T[i])
{
minf = min (minf,C[T[i]][i] - F[T[i]][i]);
}
F[*it][n] += minf;
F[n][*it] -= minf;
for (int i = *it; i != 0; i = T[i])
{
F[T[i]][i] += minf;
F[i][T[i]] -= minf;
}
}
}
for (int i=1; i<=nn; ++i)
{
for (vint it = G[i].begin (); it != G[i].end(); ++it)
{
if (F[i][*it] && *it != 0)
{
++m;
e[m].x = i;
e[m].y = *it - nn;
}
}
}
fout<<m<<"\n";
for (int i=1; i<=m; ++i)
{
fout<<e[i].x<<" "<<e[i].y<<"\n";
}
}