Pagini recente » Cod sursa (job #2528481) | Cod sursa (job #2583196) | Cod sursa (job #1807009) | Cod sursa (job #647850) | Cod sursa (job #2216912)
#include <bits/stdc++.h>
#define N 110
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
int n, IN[N], OUT[N], C[N << 1][N << 1], S, F, dad[N << 1], flow, maxflow;
vector <int> v[N << 1];
queue <int> q;
bool viz[N << 1];
bool bfs(){
memset(viz, 0, sizeof viz);
viz[S] = 1;
q.push(S);
while(q.size()){
int from = q.front();
q.pop();
if(from == F)
continue;
for(auto to : v[from]){
if(!viz[to] && C[from][to] > 0){
q.push(to);
viz[to] = 1;
dad[to] = from;
}
}
}
return viz[F];
}
int main(){
in >> n;
for(int i = 1; i <= n; i++)
in >> IN[i] >> OUT[i];
F = 2 * n + 1;
for(int i = 1; i <= n; i++){
v[S].push_back(i);
v[i].push_back(S);
v[i + n].push_back(F);
v[F].push_back(i + n);
C[S][i] = IN[i];
C[i + n][F] = OUT[i];
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
if(i == j)
continue;
v[i].push_back(n + j);
v[n + j].push_back(i);
C[i][n + j] = 1;
}
while(bfs()){
maxflow = 123456;
for(int i = F; i != S; i = dad[i])
maxflow = min(maxflow, C[dad[i]][i]);
for(int i = F; i != S; i = dad[i]){
C[dad[i]][i] -= maxflow;
C[i][dad[i]] += maxflow;
}
flow += maxflow;
}
out << flow;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j && !C[i][n + j])
out << '\n' << i << ' ' << j;
return 0;
}