Pagini recente » Cod sursa (job #3294974) | Cod sursa (job #1204082) | Cod sursa (job #1183927) | Cod sursa (job #2227334) | Cod sursa (job #1443912)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define NMax 310
#define MMax 5010
#define INF 2000000000
using namespace std;
int source, destination;
int ans;
int n, m;
int from[NMax];
vector <int> G[NMax];
int residual_graph[NMax][NMax];
int flow[NMax][NMax];
bool viz[NMax];
/// residual graph are la pozitia [i][j] pe x unde x este capacitatea - fluxul pe muchia i -> j
/// si are la pozitia [j][i] pe y unde y este fluxul pe i -> j daca acesta este > 0
inline int In(const int & x)
{
return x + n;
}
inline int Out(const int & x)
{
return x + n + n;
}
void Read()
{
ifstream f ("harta.in");
f >> n;
source = 3*n + 1;
destination = 3*n + 2;
for (int i = 1; i <= n; ++ i)
{
int x, y;
f >> x >>y;
G[source].push_back(In(i));
G[In(i)].push_back(source);
residual_graph[source][In(i)] = x;
for (int j = 1; j <= n; ++ j)
{
if (i != j)
{
G[In(i)].push_back(j);
G[j].push_back(In(i));
residual_graph[In(i)][j] = 1;
}
}
G[Out(i)].push_back(i);
G[i].push_back(Out(i));
residual_graph[i][Out(i)] = y;
G[Out(i)].push_back(destination);
G[destination].push_back(Out(i));
residual_graph[Out(i)][destination] = n;
}
f.close();
}
inline bool BFS()
{
queue <int> Q;
int i;
for (i=1; i<=3*n + 2; ++i)
from[i] = 0, viz[i] = false;
Q.push(source);
viz[source] = true;
while(!Q.empty())
{
int node = Q.front(); Q.pop();
for (vector<int>::iterator it = G[node].begin(); it!=G[node].end(); ++it)
if (!viz[*it] && residual_graph[node][*it] > 0)
{
from[*it] = node;
viz[*it] = true;
Q.push(*it);
}
}
return viz[destination];
}
void Solve()
{
while (BFS()) /// cat timp mai am cai de augmentare
{
int i;
for (i=Out(1); i<=Out(n); ++i)
if (residual_graph[i][destination] > 0 && from[i])
{
int localflow = residual_graph[i][destination];
int node = i;
while (node != source)
{
localflow = min(localflow, residual_graph[from[node]][node]);
node = from[node];
}
ans += localflow;
/// poate am saturat o muchie mai inainte in arborele BFS si acum nu mai are rost sa fac vreo ceva
if (localflow == 0)
continue;
node = i;
residual_graph[i][destination] -= localflow;
residual_graph[destination][i] += localflow;
flow[i][destination] += localflow;
while (node != source)
{
flow[from[node]][node] += localflow;
flow[node][from[node]] -= localflow;
residual_graph[from[node]][node] -= localflow;
residual_graph[node][from[node]] += localflow;
node = from[node];
}
}
}
}
void Write()
{
ofstream g("harta.out");
g<<ans<<"\n";
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
{
if (i == j)
continue;
if (flow[In(i)][j] == 1)
g << i << " " << j << "\n";
}
g.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}