Pagini recente » Cod sursa (job #1587188) | Cod sursa (job #1246730) | Cod sursa (job #2851659) | Borderou de evaluare (job #1569693) | Cod sursa (job #2962013)
#include<fstream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, m, x, y, z, s, t;
int capacitate[5001][5001];
vector<vector<int>> graf;
int tata[5001];
bool bfs(){
queue<int> q;
int vizitat[t+1];
for(int i=1 ; i<=t; i++)
vizitat[i] = 0;
q.push(s);
vizitat[s] = 1;
tata[s] = -1;
while(!q.empty()){
int u = q.front();
q.pop();
for(auto v: graf[u]){
if(vizitat[v] == 0 && capacitate[u][v] != 0){
tata[v] = u;
if(v == t)
return true;
vizitat[v] = 1;
q.push(v);
}
}
}
return false;
}
int flux_maxim(){
int fluxmax = 0;
while (bfs()){
int u, v = t, flux = INT_MAX;
while(v!=s){
u = tata[v];
if(capacitate[u][v] < flux)
flux = capacitate[u][v];
v = tata[v];
}
v = t;
while(v != s){
u = tata[v];
capacitate[u][v] -= flux;
capacitate[v][u] += flux;
v = tata[v];
}
fluxmax += flux;
}
return fluxmax;
}
int main(){
fin>>n;
s = 0;
t = 2*n + 1;
graf.resize(t+1);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i != j){
graf[i].push_back(j+n);
graf[j+n].push_back(i);
capacitate[i][j+n] = 1;
}
}
}
for(int i=1; i<=n; i++){
fin>>x>>y;
graf[s].push_back(i);
graf[i].push_back(s);
capacitate[s][i] = x;
graf[t].push_back(i+n);
graf[i+n].push_back(t);
capacitate[i+n][t] = y;
}
fout<<flux_maxim()<<"\n";
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(capacitate[j+n][i] == 1)
fout<<i<<" "<<j<<"\n";
}
}
}