Pagini recente » Cod sursa (job #1026326) | Cod sursa (job #2303183) | Cod sursa (job #684979) | Cod sursa (job #773868) | Cod sursa (job #1555728)
#include <fstream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_N = 500;
const int NIL = -1;
const int INF = 2e9;
struct Edge
{
int v, next;
int cap;
};
Edge G[2 * (MAX_N * MAX_N * 2 + 2 * MAX_N)];
int head[MAX_N];
int father[2 * MAX_N];
int edgePointer[2 * MAX_N];
int Q[2 * MAX_N];
int qStart, qEnd;
int N;
void addEdge( const int u, const int v, const int cap )
{
static int buffPtr = 0;
G[buffPtr].v = v;
G[buffPtr].cap = cap;
G[buffPtr].next = head[u];
head[u] = buffPtr++;
}
int BFS( const int source, const int sink )
{
const int numVertex = 2 * (N + 1);
for ( int i = 0; i < numVertex; i++ )
father[i] = NIL;
qStart = 0;
qEnd = 1;
Q[0] = source;
while ( qStart != qEnd && father[sink] == NIL )
{
int node = Q[qStart++];
for ( int i = head[node]; i != NIL; i = G[i].next )
{
int son = G[i].v;
if ( father[son] == NIL && G[i].cap > 0 )
{
father[son] = node;
edgePointer[son] = i;
Q[qEnd++] = son;
}
}
}
int flow = 0;
for ( int i = head[sink]; i != NIL; i = G[i].next )
{
int son = G[i].v;
if ( father[son] != NIL && G[i ^ 1].cap )
{
father[sink] = son;
edgePointer[sink] = i ^ 1;
int minFlow = INF;
int node = sink;
while ( node != source )
{
minFlow = min( minFlow, G[ edgePointer[node] ].cap );
node = father[node];
}
node = sink;
while ( node != source )
{
G[ edgePointer[node] ].cap -= minFlow;
G[ edgePointer[node] ^ 1 ].cap += minFlow;
node = father[node];
}
flow += minFlow;
}
}
return flow;
}
int main(void) {
ifstream in("harta.in");
ofstream out("harta.out");
in.tie(0);
ios_base::sync_with_stdio(0);
in >> N;
const int source = 0;
const int sink = 2 * N + 1;
for ( int i = source; i <= sink; i++ )
head[i] = NIL;
for ( int i = 1; i <= N; ++i )
{
int inDegree, outDegree;
in >> inDegree >> outDegree;
addEdge( source, 2 * i - 1, outDegree );
addEdge( 2 * i - 1, source, 0 );
addEdge( 2 * i, sink, inDegree );
addEdge( sink, 2 * i, 0 );
for ( int j = 1; j <= N; ++j )
if ( i != j )
{
addEdge( 2 * i - 1, 2 * j, 1 );
addEdge( 2 * j, 2 * i - 1, 0 );
}
}
in.close();
int flow = 0, augment;
do
{
augment = BFS( source, sink );
flow += augment;
} while ( augment != 0 );
out << flow << '\n';
for ( int i = 1; i <= N; i++ )
for ( int j = head[2 * i - 1]; j != NIL; j = G[j].next )
if ( G[j].cap == 0 )
out << G[j].v / 2 << ' ' << i << '\n';
out.close();
return 0;
}