Pagini recente » Cod sursa (job #998863) | Cod sursa (job #584288) | Cod sursa (job #1132774) | Cod sursa (job #48997) | Cod sursa (job #3188146)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define INF 999999
int N, source, target, maxFlow;
vector<vector<int>> adi, capacity, flow;
vector<int> parinte, degreeIn, degreeOut;
ifstream fin("harta.in");
ofstream fout("harta.out");
int bfs(){
queue<pair<int, int>> q;
q.push({source, INF});
while(!q.empty()){
int node = q.front().first;
int newFlow = q.front().second;
q.pop();
for(int i : adi[node]){
if(parinte[i] == -1 && capacity[node][i] > 0){
parinte[i] = node;
newFlow = min(newFlow, capacity[node][i]);
if(i == target){
return newFlow;
}
q.push({i, newFlow});
}
}
}
return 0;
}
int main()
{
fin >> N;
adi.resize(2 * N + 2);
capacity.resize(2 * N + 2, vector<int>(2 * N + 2, 0));
flow.resize(N + 1);
parinte.resize(2 * N + 2, -1);
degreeIn.resize(N + 1, 0);
degreeOut.resize(N + 1, 0);
for(int i = 1; i <= N; i++){
fin >> degreeOut[i] >> degreeIn[i];
}
source = 0;
target = 2 * N + 1;
for(int i = 1; i <= N; i++){
adi[source].push_back(i);
adi[i].push_back(source);
capacity[source][i] = degreeOut[i];
}
for(int i = N + 1; i < target; i++){
adi[target].push_back(i);
adi[i].push_back(target);
capacity[i][target] = degreeIn[i - N];
}
for(int i = 1; i <= N; i++){
for(int j = N + 1; j < target; j++){
if(i + N == j){
continue;
}
adi[i].push_back(j);
adi[j].push_back(i);
capacity[i][j] = 1;
}
}
for(int i = 0; i <= target; i++){
parinte[i] = -1;
}
parinte[source] = -2;
int c;
while(c = bfs()){
maxFlow = maxFlow + c;
int node = target;
while(node != source){
int stramos = parinte[node];
capacity[stramos][node] -= c;
capacity[node][stramos] += c;
if(node > source && node < target && stramos > source && stramos < target){
if(stramos < node){
flow[stramos].push_back(node);
}
else{
for(int i = 0; i < flow[node].size(); i++){
if(flow[node][i] == stramos){
flow[node].erase(flow[node].begin() + i);
break;
}
}
}
}
node = stramos;
}
for(int i = 0; i <= target; i++){
parinte[i] = -1;
}
parinte[source] = -2;
}
fout << maxFlow << "\n";
for(int i = 1; i <= N; i++){
for(int j : flow[i]){
fout << i << " " << j - N << "\n";
}
}
return 0;
}