Pagini recente » Cod sursa (job #1336365) | Cod sursa (job #1461166) | Cod sursa (job #2394825) | Cod sursa (job #2663732) | Cod sursa (job #2961038)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int MaxFlow(vector<vector<int>> &cap, int s, int t) {
int n = cap.size();
vector<vector<int>> flow(n, vector<int>(n));
int ans = 0;
while (true) {
vector<int> par(n, -1);
par[s] = -2;
queue<int> q;
q.push(s);
while (!q.empty() && par[t] == -1) {
int u = q.front();
q.pop();
for (int v = 0; v < n; v++) {
if (par[v] == -1 && cap[u][v] - flow[u][v] > 0) {
par[v] = u;
q.push(v);
}
}
}
if (par[t] == -1) {
break;
}
int f = INT_MAX;
for (int v = t; v != s; v = par[v]) {
f = min(f, cap[par[v]][v] - flow[par[v]][v]);
}
for (int v = t; v != s; v = par[v]) {
flow[par[v]][v] += f;
flow[v][par[v]] -= f;
}
ans += f;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(flow[i][j] > 0 && i != 0 && j != n - 1) {
fout << i << " " << j - (n/2) + 1 << "\n";
}
}
}
return ans;
}
int main() {
int n, m1 = 0, m2 = 0;
fin >> n ;
int s = 0, t = 2 * n + 1;
vector<vector<int>> cap(2*n+2, vector<int>(2 * n + 2, 0));
for(int i = 1; i <= n;i++)
{
int x, y;
fin >> x >> y;
cap[s][i] = x;
cap[i + n][t] = y;
m1 += x;
m2 += y;
}
if(m1 != m2)
{
fout << "Imposibil";
return 0;
}
for(int i = 1; i <= n;i++)
{
for(int j = n + 1; j <= 2 * n;j++)
{
if(i != j - n)
{
cap[i][j] = 1;
}
}
}
fout<< m1 << "\n";
MaxFlow(cap, s, t);
return 0;
}