Pagini recente » Istoria paginii runda/becreative4 | Istoria paginii runda/de_la_inceput/clasament | Cod sursa (job #3155025) | Cod sursa (job #2553030) | Cod sursa (job #3193837)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "harta.in" );
ofstream fout( "harta.out" );
const int DIM = 205;
const int INF = 1e9;
vector<int> G[DIM];
int cap[DIM][DIM];
int flow[DIM][DIM];
int viz[DIM];
void push_edge( int u, int v, int c ) {
if ( c == 0 ) return;
G[u].push_back(v);
G[v].push_back(u);
cap[u][v] += c;
}
int prv[DIM];
int bfs( int s, int d ) {
queue<int> q;
q.push(s);
prv[s] = 0;
while ( !q.empty() ) {
int u = q.front();
q.pop();
for ( auto v : G[u] ) {
if ( prv[v] == -1 && cap[u][v] > flow[u][v] ) {
prv[v] = u;
q.push(v);
}
}
}
return prv[d];
}
int main() {
int n, in, out;
int s, d;
fin >> n;
s = 0, d = 2 * n + 1;
for ( int i = 1; i <= n; ++i ) {
fin >> out >> in;
push_edge(s, i, out);
push_edge(i + n, d, in);
}
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= n; ++j ) {
if ( i != j ) {
push_edge(i, j + n, 1);
}
}
}
int res = 0;
while ( bfs(s, d) != -1 ) {
int win = INF;
for ( int u = d; u != s; u = prv[u] ) {
win = min(win, cap[prv[u]][u] - flow[prv[u]][u]);
}
for ( int u = d; u != s; u = prv[u] ) {
flow[prv[u]][u] += win;
flow[u][prv[u]] -= win;
}
res += win;
for ( int i = s; i <= d; ++i ) {
prv[i] = -1;
}
}
fout << res << "\n";
vector<pair<int, int>> edges;
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= n; ++j ) {
if ( flow[i][j + n] == 1 ) {
edges.push_back({i, j});
}
}
}
for ( auto [u, v] : edges ) {
fout << u << " " << v << "\n";
}
fin.close();
fout.close();
return 0;
}