Pagini recente » Cod sursa (job #2298525) | Cod sursa (job #817385) | Cod sursa (job #857191) | Cod sursa (job #844256) | Cod sursa (job #2207431)
#include <bits/stdc++.h>
using namespace std;
#if 1
#define pv(x) cout<<#x<<" = "<<(x)<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif
#ifdef INFOARENA
ifstream in("harta.in");
ofstream out("harta.out");
#else
#define in cin
#define out cout
#endif
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 2e2 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;
int cap[NMax][NMax], prv[NMax];
bool vis[NMax];
vector<int> adj[NMax];
bool bfs(int source, int dest) {
memset(vis, 0, sizeof(vis));
memset(prv, 0, sizeof(prv));
queue<int> Q;
Q.push(source);
while (Q.size()) {
int curr = Q.front(); Q.pop();
if (curr == dest) {
return true;
}
for (int nxt : adj[curr]) {
if (prv[nxt] || !cap[curr][nxt]) {
continue;
}
prv[nxt] = curr;
Q.push(nxt);
}
}
return false;
}
int main() {
cin.sync_with_stdio(false);
cin.tie(0);
int N;
in >> N;
int source = 2*N + 1, dest = 2*N + 2;
vector< pair<int,int> > deg(N+1);
for (int i = 1; i <= N; ++i) {
in >> deg[i].first >> deg[i].second;
cap[source][i] += deg[i].first;
adj[source].pb(i);
adj[i].pb(source);
cap[i + N][dest] += deg[i].second;
adj[dest].pb(i + N);
adj[i + N].pb(dest);
}
for (int i = 1; i <= N; ++i) {
for (int j = N + 1; j <= 2*N; ++j) {
if (i == j - N) {
continue;
}
cap[i][j] += 1;
adj[i].pb(j);
adj[j].pb(i);
}
}
while (bfs(source, dest)) {
int node = dest;
int minFlow = inf_int;
while (node != source) {
minFlow = min(minFlow, cap[prv[node]][node]);
node = prv[node];
}
node = dest;
while (node != source) {
cap[prv[node]][node] -= minFlow;
cap[node][prv[node]] += minFlow;
node = prv[node];
}
}
for (int i = 1; i <= N; ++i) {
for (int j = N + 1; j <= 2*N; ++j) {
if (cap[i][j] == 0) {
out << i << ' ' << j - N << '\n';
}
}
}
// out << maxFlow << '\n';
return 0;
}