Pagini recente » Borderou de evaluare (job #1591041) | Istoria paginii utilizator/corina16 | Rezultatele filtrării | Profil 7adrianc551tp0 | Cod sursa (job #1513913)
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
#include <bitset>
#define DIM 256
using namespace std;
int nrNodes, nrEdges, inside, outside;
vector <int> Edges[DIM]; int Father[DIM];
bitset <DIM> Marked; deque <int> Queue;
int Quantity[DIM][DIM], maxFlow[DIM][DIM];
bool BFS (int startNode, int finishNode)
{
Marked.reset();
Queue.clear();
int ok = 0;
Queue.push_back(startNode);
Marked[startNode] = 1;
Father[0] = -1;
while (!Queue.empty())
{
int node = Queue.front();
vector <int> :: iterator it;
for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
{
int nextNode = *it;
if (!Marked[nextNode] && maxFlow[node][nextNode] < Quantity[node][nextNode])
{
Marked[nextNode] = 1;
Father[nextNode] = node;
Queue.push_back(nextNode);
if (nextNode == finishNode)
ok = 1;
}
}
Queue.pop_front();
}
return ok;
}
int main ()
{
freopen ("harta.in" ,"r", stdin );
freopen ("harta.out","w", stdout);
scanf ("%d", &nrNodes);
int startNode = 0;
int finishNode = 2 * nrNodes + 1;
for (int i = 1; i <= nrNodes; i ++)
{
scanf ("%d %d", &outside, &inside);
Edges[startNode].push_back(i);
Edges[i].push_back(startNode);
Edges[nrNodes + i].push_back(finishNode);
Edges[finishNode].push_back(nrNodes + i);
Quantity[startNode][i] = outside;
Quantity[nrNodes + i][finishNode] = inside;
for (int j = nrNodes + 1; j <= 2 * nrNodes; j ++)
{
if (j == nrNodes + i) continue;
Edges[i].push_back(j);
Edges[j].push_back(i);
Quantity[i][j] = 1;
}
}
int sum = 0;
while ( BFS(startNode, finishNode) )
{
int node = finishNode;
vector <int> :: iterator it;
for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
{
int nextNode = *it;
if (Marked[nextNode] && maxFlow[nextNode][node] < Quantity[nextNode][node])
{
int minim = Quantity[nextNode][node] - maxFlow[nextNode][node], newNode;
newNode = nextNode;
while (Father[newNode] != -1)
{
minim = min(minim, Quantity[Father[newNode]][newNode] - maxFlow[Father[newNode]][newNode]);
newNode = Father[newNode];
}
sum += minim;
maxFlow[nextNode][node] += minim;
maxFlow[node][nextNode] -= minim;
newNode = nextNode;
while (Father[newNode] != -1)
{
maxFlow[Father[newNode]][newNode] += minim;
maxFlow[newNode][Father[newNode]] -= minim;
newNode = Father[newNode];
}
}
}
}
int nrNewEdges = 0;
for (int i = 1; i <= nrNodes; i ++)
for (int j = nrNodes + 1; j <= nrNodes * 2; j ++)
if (maxFlow[i][j] == 1) nrNewEdges ++;
printf ("%d\n", nrNewEdges);
for (int i = 1; i <= nrNodes; i ++)
for (int j = nrNodes + 1; j <= nrNodes * 2; j ++)
if (maxFlow[i][j] == 1)
printf ("%d %d\n", i, j - nrNodes);
fclose (stdin );
fclose (stdout);
return 0;
}