Pagini recente » Cod sursa (job #563106) | Cod sursa (job #707291) | Cod sursa (job #658125) | Cod sursa (job #926349) | Cod sursa (job #2957455)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define max_capacity 1e9
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, max_flow;
int capacity[202][202];
vector<int>parent, visited;
vector<int>adjacency_list[101];
queue<int>q;
int bfs(){
visited.assign(2*n+2, 0);
parent.assign(2*n+2, 0);
while(!q.empty()){
q.pop();
}
q.push(0);
visited[0]=1;
parent[0]=0;
while(!q.empty()){
int node=q.front();
q.pop();
for(auto neighbour:adjacency_list[node]){
if(visited[neighbour]==0 && capacity[node][neighbour]>0) {
q.push(neighbour);
parent[neighbour]=node;
visited[neighbour]=1;
if(neighbour == 2*n+1) return 1;
}
}
}
return visited[2*n+1];
}
int main() {
int x, y, z;
fin>>n;
for(int i=1; i<=n; i++){
fin>>x>>y;
z = n;
adjacency_list[0].push_back(i);
adjacency_list[i].push_back(0);
adjacency_list[2*n+1].push_back(n+i);
adjacency_list[n+i].push_back(2*n+1);
capacity[0][i]=x;
capacity[n+i][2*n+1]=y;
}
for(int i=1; i<=n; i++){
for(int j=n+1; j<=2*n; j++){
if(j != n+i){
adjacency_list[i].push_back(j);
adjacency_list[j].push_back(i);
capacity[i][j]=1;
}
}
}
while(bfs()) {
for (auto node: adjacency_list[2*n+1]) {
if (!visited[node])
continue;
parent[2*n+1] = node;
int flow = max_capacity;
for (node = 2*n+1; node != 0; node = parent[node]) {
flow = min(flow, capacity[parent[node]][node]);
}
if (flow == 0) continue;
for (node = 2*n+1; node != 0; node = parent[node]) {
capacity[parent[node]][node] -= flow;
capacity[node][parent[node]] += flow;
}
max_flow += flow;
}
}
fout<<max_flow<<'\n';
for(int i=1; i<=n; i++){
for(int j=n+1; j<=2*n+1; j++){
if(capacity[i][j] == 0 && capacity[j][i] == 1){
fout<<i<<" "<<j-n<<'\n';
}
}
}
fin.close();
fout.close();
return 0;
}