Pagini recente » Cod sursa (job #940732) | Atasamentele paginii Profil Alex_Neacsu | Cod sursa (job #793019) | Cod sursa (job #1657409) | Cod sursa (job #3329911)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int OFF = 100, NMAX = 2 * OFF + 9;
const int HIGH = 1000001;
struct graph
{
int N, M, flow[NMAX][NMAX], cap[NMAX][NMAX];
vector<int> A[NMAX];
void ae(int x, int y, int c)
{
cap[x][y] = c;
A[x].push_back(y);
A[y].push_back(x);
}
} G;
struct flow_bfs
{
bool viz[NMAX];
int tata[NMAX], sent_flow;
void clear(int N)
{
sent_flow = HIGH;
for(int i = 1; i <= N; i++)
viz[i] = false, tata[i] = 0;
}
void find_path(graph& G, int s, int t)
{
clear(G.N);
queue<int> q;
q.push(s);
viz[s] = true;
while(!q.empty())
{
int n = q.front();
q.pop();
for(const auto& v : G.A[n])
{
if(!viz[v] && G.cap[n][v] - G.flow[n][v] > 0)
{
viz[v] = true;
q.push(v);
tata[v] = n;
}
}
}
}
void run(graph& G, int s, int t)
{
find_path(G, s, t);
if(viz[t] == 0)
sent_flow = 0;
else
{
vector<int> path;
while(t != 0)
{
path.push_back(t);
t = tata[t];
}
reverse(path.begin(), path.end());
for(int i = 0; i < path.size() - 1; i++)
{
int x = path[i], y = path[i + 1];
sent_flow = min(sent_flow, G.cap[x][y] - G.flow[x][y]);
}
for(int i = 0; i < path.size() - 1; i++)
{
int x = path[i], y = path[i + 1];
G.flow[x][y] += sent_flow;
G.flow[y][x] -= sent_flow;
}
}
}
};
int edmonds_karp(graph& G, int s, int t)
{
flow_bfs B;
int max_flow = 0;
do
{
B.run(G, s, t);
max_flow += B.sent_flow;
}
while(B.sent_flow > 0);
return max_flow;
}
int main()
{
ifstream fin("harta.in");
ofstream fout("harta.out");
int dp[OFF + 1], dn[OFF + 1];
int n, s, t;
fin >> n;
G.N = 2 * OFF + 2;
s = 2 * OFF + 1;
t = 2 * OFF + 2;
for(int i = 1; i <= n; i++)
fin >> dp[i] >> dn[i];
for(int i = 1; i <= n; i++)
for(int j = 1 + OFF; j <= n + OFF; j++)
if(abs(i - j) != OFF)
G.ae(i, j, 1);
for(int i = 1; i <= n; i++)
G.ae(s, i, dp[i]);
for(int i = 1; i <= n; i++)
G.ae(i + OFF, t, dn[i]);
int e = edmonds_karp(G, s, t);
fout << e << '\n';
for(int i = 1; i <= G.N - 2; i++)
for(int j = 1; j <= G.N - 2; j++)
if(G.flow[i][j] > 0)
fout << i << ' ' << j - OFF << '\n';
fin.close();
fout.close();
return 0;
}