Pagini recente » Cod sursa (job #411241) | Cod sursa (job #114752) | Cod sursa (job #2952436) | Cod sursa (job #2932142) | Cod sursa (job #2620805)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
vector<int> graf[MAXN];
queue<int> coada;
int flux[MAXN][MAXN], sursa[MAXN];
bool viz[MAXN];
int n, s, d;
int main()
{
ifstream fin("harta.in");
ofstream fout("harta.out");
fin >> n;
s = 0; d = 2 * n + 1;
for(int i = 1; i <= n; ++i){
int out, in;
fin >> out >> in;
flux[s][i] = out; flux[i + n][d] = in;
graf[s].push_back(i); graf[i].push_back(s);
graf[i + n].push_back(d); graf[d].push_back(i + n);
}
for(int i = 1; i <= n; ++i){
for(int j = n + 1; j <= 2 * n; ++j){
if(i == j - n) continue;
flux[i][j] = 1;
graf[i].push_back(j); graf[j].push_back(i);
}
}
bool sink = 1;
while(sink){
sink = 0;
memset(viz, 0, 2 * n + 2);
coada.push(s);
while(!coada.empty()){
int x = coada.front();
coada.pop();
for(auto y: graf[x]){
if(!viz[y] && flux[x][y] > 0){
viz[y] = 1;
sursa[y] = x;
if(y == d) sink = 1;
else coada.push(y);
}
}
}
for(auto x: graf[d]){
if(!viz[x] || flux[x][d] == 0) continue;
int mnflux = 1e9;
sursa[d] = x;
for(int crt = d; crt > s; crt = sursa[crt]) mnflux = min(mnflux, flux[sursa[crt]][crt]);
for(int crt = d; crt > s; crt = sursa[crt]){
flux[sursa[crt]][crt] -= mnflux;
flux[crt][sursa[crt]] += mnflux;
}
}
}
int m = 0;
for(int i = 1; i <= n; ++i){
for(int j = n + 1; j <= 2 * n; ++j)
if(i != j - n && flux[i][j] == 0) m++;
}
fout << m << "\n";
for(int i = 1; i <= n; ++i){
for(int j = n + 1; j <= 2 * n; ++j)
if(i != j - n && flux[i][j] == 0) fout << i << " " << j - n << "\n";
}
return 0;
}