Pagini recente » Cod sursa (job #230662) | Cod sursa (job #2906300) | Cod sursa (job #2252278) | Cod sursa (job #2749556) | Cod sursa (job #3187862)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 205;
const int INF = (1<<29);
class Graph{
private:
int noduri;
vector<vector<int>> adjList;
vector<vector<int>> flux;
vector<vector<int>> cap;
vector<int> tata;
vector<bool> ver;
public:
Graph(int nr_noduri){
this->noduri = nr_noduri;
initGraph(nr_noduri+5);
}
void initGraph(int N){
adjList.resize(N);
flux.resize(N, vector<int>(N,0));
cap.resize(N, vector<int>(N,0));
tata.resize(N);
ver.resize(N, false);
}
void pushBidirectional(int x,int y){
adjList[x].push_back(y);
adjList[y].push_back(x);
}
void setCapacity(int x,int y,int val){
cap[x][y] = val;
}
int getFlux(int x,int y){
return flux[x][y];
}
bool bfs(){
for(int i=0;i<=this->noduri;i++)
ver[i] = false;
ver[0] = true;
queue<int> q;
q.push(0);
while(!q.empty()){
int node = q.front();
q.pop();
for(int i=0;i<adjList[node].size();i++){
int vecin = adjList[node][i];
if(ver[vecin] == false and cap[node][vecin] > flux[node][vecin]){
ver[vecin] = true;
tata[vecin] = node;
q.push(vecin);
}
}
}
if(ver[this->noduri] == true) return true;
return false;
}
int getGraphFlux(){
int rasp = 0;
while(bfs()){
for(int i=0;i<adjList[this->noduri].size();i++){
int node = adjList[this->noduri][i];
if(ver[node] == true and cap[node][this->noduri] > flux[node][this->noduri]){
int minim = cap[node][this->noduri] - flux[node][this->noduri];
int naux = node;
while(naux!=0){
int t = tata[naux];
if(cap[t][naux] - flux[t][naux] < minim)
minim = cap[t][naux] - flux[t][naux];
naux = tata[naux];
}
if(minim == 0) continue;
rasp += minim;
flux[node][this->noduri] += minim;
flux[this->noduri][node] -= minim;
naux = node;
while(naux!=0){
int t = tata[naux];
flux[t][naux] += minim;
flux[naux][t] -= minim;
naux = tata[naux];
}
}
}
}
return rasp;
}
};
int n,N,x,y;
int main(){
fin >> n;
N = 2*n+1;
Graph g(N);
for(int i=1;i<=n;i++){
fin >> x >> y;
g.pushBidirectional(0,i);
g.setCapacity(0,i,x);
g.pushBidirectional(n+i,N);
g.setCapacity(n+i,N,y);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i == j) continue;
g.pushBidirectional(i,n+j);
g.setCapacity(i,n+j,1);
}
}
int rasp = g.getGraphFlux();
fout << rasp << '\n';
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g.getFlux(i,j+n) == 1){
fout << i << ' ' << j << '\n';
}
}
}
return 0;
}