Pagini recente » Cod sursa (job #1329039) | Cod sursa (job #2144562) | Cod sursa (job #1942508) | Cod sursa (job #858339) | Cod sursa (job #3186018)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
// #define f cin
// #define g cout
const int source = 0, dest = 204;
int cap[205][205], n;
vector<int> adj[205];
inline int flip(int poz)
{
if (poz <= 100)
return poz + 100;
return poz - 100;
}
void insert_edge(int from, int to, int val)
{
adj[from].push_back(to);
adj[to].push_back(from);
cap[from][to] = val;
cap[to][from] = 0;
}
vector<int> parent;
int bfs(vector<int> &parent)
{
parent.assign(205, -1);
parent[source] = -2;
queue<pair<int, int>> q;
q.push({source, INT_MAX / 8});
for (int ax, flow, new_flow; !q.empty();)
{
tie(ax, flow) = q.front();
q.pop();
for (int next : adj[ax])
if (parent[next] == -1 && cap[ax][next])
{
parent[next] = ax;
new_flow = min(flow, cap[ax][next]);
if (next == dest)
return new_flow;
q.push({next, new_flow});
}
}
return 0;
}
int main()
{
f >> n;
int ans = 0;
for (int i = 1, vin, vout; i <= n; i++)
{
f >> vout >> vin;
ans += vout;
insert_edge(source, i, vout);
insert_edge(flip(i), dest, vin);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
insert_edge(i, flip(j), 1);
for (int new_flow, ax, prev; new_flow = bfs(parent);)
{
ax = dest;
while (ax != source)
{
prev = parent[ax];
cap[prev][ax] -= new_flow;
cap[ax][prev] += new_flow;
ax = parent[ax];
}
}
g << ans << '\n';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && !cap[i][flip(j)])
g << i << " " << j << '\n';
return 0;
}