Pagini recente » Monitorul de evaluare | Cod sursa (job #543973) | Cod sursa (job #1356883) | Cod sursa (job #2742343) | Cod sursa (job #1714239)
using namespace std;
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define Nmax 210
#define INF 2000000000
int n, sum, S, T;
int f[Nmax][Nmax], c[Nmax][Nmax], pred[Nmax];
vector< int > G[Nmax];
vector< bool > vis(Nmax);
queue< int > Q;
void read();
void compute_flow();
void write();
bool BFS();
void edge(int, int);
int main()
{
read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j)
c[i][n + j] = 1,
edge(i, n + j);
compute_flow();
write();
return 0;
}
void read()
{
int i, din, dout;
ifstream fin("harta.in");
fin >> n;
S = 0; T = 2 * n + 1;
for (i = 1; i <= n; ++i)
{
fin >> dout >> din;
sum += din;
edge(S, i);
c[S][i] = dout;
edge(n + i, T);
c[n + i][T] = din;
}
fin.close();
}
void compute_flow()
{
int v, minF;
while (BFS())
{
for (auto node : G[T])
{
pred[T] = node;
for (minF = INF, v = T; v != S; v = pred[v])
if (c[pred[v]][v] - f[pred[v]][v] < minF)
minF = c[pred[v]][v] - f[pred[v]][v];
if (minF)
{
for (v = T; v != S; v = pred[v])
f[pred[v]][v] += minF,
f[v][pred[v]] -= minF;
}
}
}
}
void write()
{
ofstream fout("harta.out");
fout << sum << '\n';
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (f[i][n + j])
fout << i << ' ' << j << '\n';
fout.close();
}
bool BFS()
{
int v;
fill(vis.begin(), vis.end(), false);
for (Q.push(S), vis[S] = true; !Q.empty(); Q.pop())
{
v = Q.front();
if (v == T) continue;
for (auto &to : G[v])
if (!vis[to] && c[v][to] > f[v][to])
{
pred[to] = v;
Q.push(to);
vis[to] = true;
}
}
return vis[T];
}
void edge(int a, int b)
{
G[a].push_back(b);
G[b].push_back(a);
}