Pagini recente » Cod sursa (job #443354) | Cod sursa (job #2036648) | Cod sursa (job #1687632) | Atasamentele paginii Clasament oji-2015-cls11-12124151 | Cod sursa (job #1555745)
/*
* Metoda:
* Se contureaza reteaua astfel:
* Fiecarui nod i (1 <= i <= N) din graful cautat ii corespund 2 noduri in retea:
* Nodul 2 * i - 1, nodul de iesire
* Nodul 2 * i, nodul de intrare
* * * * * * * * * * * * * * * *
* Capacitatile vor fi conturate astfel (considerand super-sursa nodul 0, iar super-destinatia nodul 2 * N + 1):
* Arcele super-sursa -> nod iesire vor avea capacitatea = gradul de iesire al nodului respectiv
* Arcele nod intrare -> super-destinatie vor avea capacitatea = gradul de intrare al nodului respectiv
* Arcele nod iesire -> nod intrare vor avea capacitatea = 1
* Problema se reduce la gasirea fluxului maxim.
*/
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 100;
const int NIL = -1;
const int INF = 2e9;
struct Edge
{
int v, next;
int cap;
};
Edge G[4 * MAX_N * MAX_N + 4 * MAX_N]; // liste, overkill ..
int head[2 * MAX_N];
int father[2 * MAX_N]; // vector de tati pentru arborele BFS
int edgePointer[2 * MAX_N]; // pointer catre muchia din arborele BFS
int Q[2 * MAX_N]; // coada BFS
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 )
{
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 && ( G[j].v / 2 >= 1 && G[j].v / 2 <= N ) )
out << G[j].v / 2 << ' ' << i << '\n';
out.close();
return 0;
}